The Setting
A scheduling subproblem selects jobs within a region of the job set . A global extension must agree with that selection on while satisfying precedence closure throughout . Let be the precedence relation in the working frame and its rank function; the region is arbitrary. A global upset is a set containing whenever and .✦ A global downset for is an upset for the reversed relation .
Global Lists and Descriptions
An atomic family assigns a subset of to each atom. A Boolean structural formula over is a signed atomic leaf or a conjunction or disjunction of two such formulas.✦ The interpretation of a Boolean structural formula over the atomic family is the subset of obtained by assigning to a positive leaf and to a negative leaf, with conjunction and disjunction interpreted as intersection and union.✦ The leaf count of a Boolean structural formula is the number obtained by counting one at a leaf and summing the two counts at either binary operation.✦ A bounded Boolean description of with allowance is a Boolean structural formula whose interpretation is and whose leaf count is at most ; (1) states that such a description exists: (1)✦
An indexed global set family on consists of a finite set of listed indices and an entry for every .✦ The global entry union of an indexed global set family on is the subset of given by (2): (2) An indexed global set family on , with listed indices and entries , has upward-closed list entries when each with is a global upset for .
The rank upper tail at threshold is the set in (3): (3)✦ The global list suffix of an indexed global set family , for cutoffs , is the indexed global set family obtained by discarding listed indices below , replacing the entry at by when is listed, and retaining entries above . Write for its global entry union.
Boundaries and Run Certificates
A job triple in is a finite set of three jobs.✦ A scheduling triple boundary is a left endpoint, an actual job triple, or a right endpoint.✦ For an actual boundary given by a job triple in , the strict predecessor and successor cones and and the weak cones and are the subsets of defined by (4): (4) At the left endpoint both predecessor cones are empty and both successor cones are ; at the right endpoint these assignments are reversed. The atomic family has atomic predicate expressiveness for when , the empty set, every rank upper tail, all four cones of every boundary, and every job triple each have a one-leaf description.✦
A rank threshold run certificate for is a family of base sets and thresholds , together with a distinguished second set , satisfying (5): (5)✦
The Claim
Theorem 1. Let have a rank threshold run certificate on and at most five listed indices. Suppose its listed entries and its second set are global upsets for , and always gives . Suppose every rank upper tail and the empty set have one-leaf descriptions. There is a global upset satisfying (6): (6)✦
Assume additionally that is transitive and has atomic predicate expressiveness for . For every scheduling triple boundary and cutoffs , there is a global downset satisfying (7): (7)✦
In the paper, the result reads: for an already constructed edge from parent to child in its old working frame, its low cutoff has a global downset extension agreeing with it on all of and having at most leaves.
What Is Checked
The extension statements are over indexed global set families and rank threshold run certificates on , with upward closure, strict rank growth and atomic description hypotheses; the carried low cutoff also uses a scheduling triple boundary and transitive precedence.