OctoInformBeta

OpenAI preprint, September 2026 · §4. Separators with a shared cutoff

Corollary 4.5: An occupied cutoff on the whole job set, and rearrangement confined to an open time window

Rearranging full schedules to separate ideals.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let JJ be a finite set of unit jobs with precedence relation rr. A layout pp of JJ is a bijection from JJ to the positions 0,…,|J|−10,\ldots,|J|-1.✦ Jobs are grouped into consecutive triples, and the slot τp(x)\tau_p(x) of a job xx is given by (1). τp(x)=⌊p(x)3⌋+1.\tau_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(1)✦

A precedence-feasible layout pp of JJ is a layout satisfying (2). r(x,y)⇒τp(x)<τp(y)(x,y∈J).r(x,y)\ \Longrightarrow\ \tau_p(x)<\tau_p(y) \qquad (x,y\in J).(2)✦ A full schedule pp of JJ for rr is a precedence-feasible layout with |J||J| divisible by three. For a full schedule write |J|=N=3T|J|=N=3T.

A relative precedence ideal SS on a set W⊆JW\subseteq J is a set of jobs from JJ satisfying (3). x,y∈W,r(x,y),y∈S⇒x∈S.x,y\in W,\quad r(x,y),\quad y\in S \quad\Longrightarrow\quad x\in S.(3)✦

For a time assignment τ:J→ℕ\tau:J\to\mathbb N and a cutoff s∈ℕs\in\mathbb N, the cutoff predecessor and successor cones Ps(τ)P_s(\tau) and Ds(τ)D_s(\tau) are the sets in (4). Ps(τ)={x∈J:∃y∈J,τ(y)=s and r(x,y)},Ds(τ)={x∈J:∃y∈J,τ(y)=s and r(y,x)}.\begin{aligned} P_s(\tau)&=\{x\in J:\exists y\in J,\ \tau(y)=s\text{ and }r(x,y)\},\\ D_s(\tau)&=\{x\in J:\exists y\in J,\ \tau(y)=s\text{ and }r(y,x)\}. \end{aligned}(4)

Earlier high job coverage for SS on WW at cutoff ss is the condition (5). {x∈W:τ(x)<s,x∉S}⊆Ps(τ).\{x\in W:\tau(x)<s,\ x\notin S\}\subseteq P_s(\tau).(5)✦ Later low job coverage for SS on WW at cutoff ss is the condition (6). {x∈W:s<τ(x),x∈S}⊆Ds(τ).\{x\in W:s<\tau(x),\ x\in S\}\subseteq D_s(\tau).(6)✦ A shared cutoff separator ss for SS on WW is a cutoff satisfying both (5) and (6); write Sep⁡(W,r,τ,S;s)\operatorname{Sep}(W,r,\tau,S;s).✦ An actual separator ss for SS on WW is a shared cutoff separator whose cutoff is occupied by a job.

For a time assignment τ:J→ℕ\tau:J\to\mathbb N and boundary slots a,b∈ℕa,b\in\mathbb N, the open scheduling window W=(a,b)W=(a,b) is the set of jobs xx with a<τ(x)<ba<\tau(x)<b; for the time assignment of a layout pp, it is given by (7). W=(a,b)={x∈J:a<τp(x)<b}.W=(a,b)=\{x\in J:a<\tau_p(x)<b\}.(7) A layout qq of JJ is unchanged outside WW relative to pp when (8) holds. q(x)=p(x)(x∈J\W).q(x)=p(x)\qquad(x\in J\setminus W).(8)✦

The Claim

Theorem 1. Let rr be a transitive precedence relation on a finite job set JJ, and let pp be a full schedule for rr.

Suppose JJ is nonempty and SS is a precedence ideal on JJ. There are a full schedule qq for rr and a cutoff ss satisfying (9). s∈τq(J),Sep⁡(J,r,τq,S;s).s\in\tau_q(J),\qquad \operatorname{Sep}(J,r,\tau_q,S;s).(9)✦

Suppose W=(a,b)W=(a,b) is a nonempty open scheduling window of pp and SS is a relative precedence ideal on WW. There are a full schedule qq for rr and a cutoff ss satisfying (10). a<s<b,Sep⁡(W,r,τq,S;s),q(x)=p(x)(x∈J\W).a<s<b,\qquad \operatorname{Sep}(W,r,\tau_q,S;s),\qquad q(x)=p(x)\quad(x\in J\setminus W).(10)✦

In the paper, the result reads: every ideal SS of a nonempty set JJ with a full schedule has an actual separator in some full schedule of JJ.

What Is Checked

The statements concern full schedules for transitive precedence relations on finite job sets, with a nonempty domain consisting of the whole job set or of an open scheduling window, and relative precedence ideals on that domain.