OctoInformBeta

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

Lemma 4.2: Boundary separation persists when precedence and layout order are reversed

Separators describe the jobs before a cutoff.

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

A domain of jobs may be classified as low or high without following their order in a schedule. A shared cutoff constrains the jobs whose classification falls on the other side of their scheduling time. The question is how this classification describes the part of the domain before the cutoff.

Let JJ be a job set, ≺\prec a precedence relation, and t:J→ℕt:J\to\mathbb N a time assignment. A time assignment t:J→ℕt:J\to\mathbb N respects precedence ≺\prec when every pair of jobs xx and yy in JJ with x≺yx\prec y satisfies t(x)<t(y)t(x)<t(y). Let W⊆JW\subseteq J be the domain, and let S⊆JS\subseteq J be the prescribed low set, with jobs outside SS called high. A set H⊆JH\subseteq J is a candidate description of the low jobs on WW.

For a time assignment tt on a job set JJ, the cutoff predecessor set PsP_s, cutoff successor set DsD_s and cutoff set CsC_s at time ss are the subsets of JJ defined in (1). Ps={x∈J:∃y∈J,t(y)=s and x≺y},Ds={x∈J:∃y∈J,t(y)=s and y≺x},Cs={x∈J:t(x)=s}.\begin{aligned} P_s&=\{x\in J:\exists y\in J,\ t(y)=s\text{ and }x\prec y\},\\ D_s&=\{x\in J:\exists y\in J,\ t(y)=s\text{ and }y\prec x\},\\ C_s&=\{x\in J:t(x)=s\}. \end{aligned}(1)

Earlier high job coverage on a finite domain WW is the first condition in (2)✦; later low job coverage is the second.✦ A shared cutoff separator ss for WW, relative to ≺\prec, tt and SS, is a cutoff satisfying both conditions in (2), each required for every job xx. x∈W,t(x)<s,x∉S⇒x∈Ps,x∈W,s<t(x),x∈S⇒x∈Ds.\begin{aligned} &x\in W,\quad t(x)<s,\quad x\notin S &&\Longrightarrow x\in P_s,\\ &x\in W,\quad s<t(x),\quad x\in S &&\Longrightarrow x\in D_s. \end{aligned}(2)✦

The cutoff prefix test As(H)A_s(H) for a set HH of jobs in JJ at cutoff ss is the subset of JJ defined by (3). As(H)=Ps∪(H\(Ds∪Cs)).A_s(H)=P_s\cup\bigl(H\setminus(D_s\cup C_s)\bigr).(3)✦

Triple Boundaries

A job triple Z⊆JZ\subseteq J is a set of cardinality three.✦ A scheduling triple boundary BB is a left endpoint ℓ\ell, an actual job triple ZZ, or a right endpoint rr.✦ The strict predecessor cone PBP_B, strict successor cone DBD_B and weak successor cone DB+D_B^+ of a scheduling triple boundary BB on JJ are the subsets of JJ in (4), all taken under ≺\prec. Pℓ=⌀,Dℓ=Dℓ+=J,Pr=J,Dr=Dr+=⌀,PZ={x∈J:∃z∈Z,x≺z},DZ={x∈J:∃z∈Z,z≺x},DZ+=DZ∪Z.\begin{aligned} P_\ell&=\varnothing,&D_\ell=D_\ell^+&=J,\\ P_r&=J,&D_r=D_r^+&=\varnothing,\\ P_Z&=\{x\in J:\exists z\in Z,\ x\prec z\},\\ D_Z&=\{x\in J:\exists z\in Z,\ z\prec x\}, &D_Z^+&=D_Z\cup Z. \end{aligned}(4)

A boundary BB is at cutoff ss for time assignment tt and horizon TT when (5) holds. {s=0,B=ℓ,1≤s≤T and Z=Cs,B=Z,s=T+1,B=r.\begin{cases} s=0,&B=\ell,\\ 1\le s\le T\ \text{ and }\ Z=C_s,&B=Z,\\ s=T+1,&B=r. \end{cases}(5)✦

A boundary BB separates WW at cutoff ss relative to SS when the conditions in (6) hold for every job xx.✦ Write Sep⁡B(≺,t,W,S,s)\operatorname{Sep}_B(\prec,t,W,S,s) for this separation condition. x∈W,t(x)<s,x∉S⇒x∈PB,x∈W,s<t(x),x∈S⇒x∈DB.\begin{aligned} &x\in W,\quad t(x)<s,\quad x\notin S &&\Longrightarrow x\in P_B,\\ &x\in W,\quad s<t(x),\quad x\in S &&\Longrightarrow x\in D_B. \end{aligned}(6)

The boundary prefix set ℬB(H)\mathcal B_B(H) consists of the strict predecessors of BB together with the jobs of HH outside its weak successor cone, as in (7). ℬB(H)=PB∪(H\DB+).\mathcal B_B(H)=P_B\cup(H\setminus D_B^+).(7)✦

Reversal

For a finite job set JJ of size NN, a layout pp is a bijection from JJ to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ For a layout pp of a finite job set JJ of size NN and a job xx in JJ, the time slot tp(x)t_p(x) is the positive integer defined in (8). The reversed layout prevp^{\mathrm{rev}} of a layout pp on JJ is the bijection from JJ to the positions 0,…,N−10,\ldots,N-1 defined in (8). tp(x)=⌊p(x)3⌋+1,prev(x)=N−1−p(x).t_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad p^{\mathrm{rev}}(x)=N-1-p(x).(8)

The reversed precedence relation ≺rev\prec^{\mathrm{rev}} on JJ is the relation given by x≺revyx\prec^{\mathrm{rev}}y when y≺xy\prec x. The reversed boundary BrevB^{\mathrm{rev}} of a scheduling triple boundary BB is the boundary obtained by exchanging ℓ\ell and rr and fixing every actual triple.✦ The reversed working frame uses ≺rev\prec^{\mathrm{rev}} and time tprevt_{p^{\mathrm{rev}}}, in place of the original precedence and layout time tpt_p.

The Claim

Theorem 1. Let WW be finite. Suppose tt respects ≺\prec, ss is a shared cutoff separator for WW relative to SS, and H∩W=S∩WH\cap W=S\cap W. For each x∈Wx\in W, the cutoff description is (9). x∈As(H)⇔t(x)<s.x\in A_s(H)\quad\Longleftrightarrow\quad t(x)<s.(9)✦

Suppose instead that 1≤t(x)≤T1\le t(x)\le T for every x∈Jx\in J, tt respects ≺\prec, BB is at cutoff ss for horizon TT, BB separates WW at ss relative to SS, and H∩W=S∩WH\cap W=S\cap W. For each x∈Wx\in W, the boundary description is (10). x∈ℬB(H)⇔t(x)<s.x\in\mathcal B_B(H)\quad\Longleftrightarrow\quad t(x)<s.(10)✦

Let JJ be finite with N=|J|=3TN=|J|=3T, let pp be a layout, and let 0≤s≤T+10\le s\le T+1. If BB separates WW at ss relative to SS, using precedence ≺\prec and time tpt_p, then (11) holds. Sep⁡Brev(≺rev,tprev,W,J\S,T+1−s).\operatorname{Sep}_{B^{\mathrm{rev}}} \bigl(\prec^{\mathrm{rev}},t_{p^{\mathrm{rev}}},W,J\setminus S,T+1-s\bigr).(11)✦

In the paper, the result reads: if an actual separator zz for WW has cutoff set SS and H∩W=SH\cap W=S, then ℬz(H)∩W\mathcal B_z(H)\cap W is exactly the domain jobs strictly before zz, and reversing order and time while exchanging low with high preserves separation.

What Is Checked

The descriptions concern sets HH agreeing with SS on WW and time assignments respecting precedence, with a finite domain and a shared cutoff separator for (9), or positive times bounded by TT and a separating boundary at the cutoff for (10); (11) concerns layouts on N=3TN=3T jobs, a separating boundary and 0≤s≤T+10\le s\le T+1.