OctoInformBeta

OpenAI preprint, September 2026 · §2. Sweeps, activity, and exchange graphs

Lemma 2.4: Supporting lines constrain edge classes labeled by exchange endpoints

Exchange edge partitions control the number of crossings.

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

As a separating line changes slope, points leave and enter a marked set of fixed size. The exchange graph joins every departing point to every entering point in the same batch.✦ The question is how partitions of the exchange edges into classes constrained by supporting lines control the number of crossings.

Let In={0,…,n−1}I_n=\{0,\ldots,n-1\}, and let P:In→ℝ2P:I_n\to\mathbb R^2 be a configuration, with Pi=(xi,yi)P_i=(x_i,y_i). The sweep projection at slope ss is the linear functional πs\pi_s in (1). πs(x,y)=y−sx.\pi_s(x,y)=y-sx.(1)✦ A slope ss separates a marked set M⊆InM\subseteq I_n when every marked point has smaller projection than every unmarked point.✦

A uniform exchange system 𝒮\mathcal S with parameters R,k,aR,k,a consists of sample slopes s0,…,sRs_0,\ldots,s_R and marked sets M0,…,MR⊆InM_0,\ldots,M_R\subseteq I_n satisfying (2), including separation at every sample and exchange distance aa between consecutive samples. s0<⋯<sR,|Mb|=k(0≤b≤R),πsb(Pi)<πsb(Pj)(i∈Mb,j∉Mb),|Mb\Mb+1|=a(0≤b<R).\begin{gathered} s_0<\cdots<s_R,\qquad |M_b|=k\quad(0\le b\le R),\\ \pi_{s_b}(P_i)<\pi_{s_b}(P_j) \quad(i\in M_b,\ j\notin M_b),\\ |M_b\setminus M_{b+1}|=a\quad(0\le b<R). \end{gathered}(2)✦ The leaving set LbL_b and entering set GbG_b of batch bb are the differences in (3). Lb=Mb\Mb+1,Gb=Mb+1\Mb(0≤b<R).L_b=M_b\setminus M_{b+1},\qquad G_b=M_{b+1}\setminus M_b \quad(0\le b<R).(3)

Let EE be the exchange edge set, let VV be its endpoint set, and let SS denote the number of these endpoints. E=⋃b=0R−1(Lb×Gb),V={i:(i,j)∈E}∪{j:(i,j)∈E},S=|V|.E=\bigcup_{b=0}^{R-1}(L_b\times G_b),\qquad V=\{i:(i,j)\in E\}\cup\{j:(i,j)\in E\},\qquad S=|V|.(4) A straight-line drawing DD of a configuration PP is a geometric graph with finite vertex and ordered edge sets, with both endpoints of every edge among its vertices and xi<xjx_i<x_j for every edge (i,j)(i,j). The exchange drawing DD has vertex set VV, edge set EE, and edge segments [Pi,Pj][P_i,P_j].✦

Two edges cross when their open segments intersect.✦ Write 𝒞(D)\mathcal C(D) for the set of distinct unordered crossing edge pairs.✦ A straight-line drawing DD has no triple edge intersections when a point in the open segments of two distinct edges belongs to no third edge segment, including its endpoints.✦

A configuration PP is in general position when its points are distinct and no three are collinear.✦ Collinearity is measured by the orientation determinant (5). orient⁡(p,q,r)=det⁡(q−p,r−p)=(q1−p1)(r2−p2)−(q2−p2)(r1−p1).\operatorname{orient}(p,q,r) =\det(q-p,r-p) =(q_1-p_1)(r_2-p_2)-(q_2-p_2)(r_1-p_1).(5)✦ A configuration PP, with Pi=(xi,yi)P_i=(x_i,y_i), has distinct abscissae when i↦xii\mapsto x_i is injective; this is a separate condition from general position.

Owners and Supporting Lines

Assume n,a>0n,a>0 and put J={0,…,a−1}J=\{0,\ldots,a-1\}, with addition modulo aa. Fix bijective enumerations ℓb:Lb→J\ell_b:L_b\to J and gb:Gb→Jg_b:G_b\to J. The cyclic perfect matching mj,b:Lb→Gbm_{j,b}:L_b\to G_b with shift j∈Jj\in J is (6). mj,b(u)=gb−1(ℓb(u)+j).m_{j,b}(u)=g_b^{-1}\bigl(\ell_b(u)+j\bigr).(6) For finite sets M,M′M,M' and a bijection m:M\M′→M′\Mm:M\setminus M'\to M'\setminus M, the matching-induced transport is the bijection M→M′M\to M' which fixes M∩M′M\cap M' and sends each leaving element uu to m(u)m(u).

The batch token transport Tj,b:Mb→Mb+1T_{j,b}:M_b\to M_{b+1} is the transport induced by mj,bm_{j,b}.✦ The cumulative token transport Uj,b:M0→MbU_{j,b}:M_0\to M_b is the composition specified in (7). Uj,0=id⁡M0,Uj,b+1=Tj,b∘Uj,b.U_{j,0}=\operatorname{id}_{M_0},\qquad U_{j,b+1}=T_{j,b}\circ U_{j,b}.(7)✦ An edge token trace of e=(i,i′)e=(i,i') is a triple (b,j,u)(b,j,u), where 0≤b<R0\le b<R, j∈Jj\in J and u∈M0u\in M_0, satisfying (8). Uj,b(u)=i∈Lb,Uj,b+1(u)=i′∈Gb.U_{j,b}(u)=i\in L_b,\qquad U_{j,b+1}(u)=i'\in G_b.(8)✦ For a choice of one trace t(e)=(be,je,ue)t(e)=(b_e,j_e,u_e) for each e∈Ee\in E, the convex owner ω+\omega_+ is the map on EE given by ω+(e)=(je,ue)\omega_+(e)=(j_e,u_e).

The complementary reflected system 𝒮ˆ\widehat{\mathcal S} of 𝒮\mathcal S is the exchange system obtained by replacing PiP_i by −Pi-P_i and MbM_b by In\MbI_n\setminus M_b, keeping the sample slopes and exchange distance and replacing the mark count kk by n−kn-k.✦ The concave owner ω−\omega_- of 𝒮\mathcal S is the owner map defined from the convex owner ωˆ+\widehat\omega_+ of 𝒮ˆ\widehat{\mathcal S} by (9). ω−(i,i′)=ωˆ+(i′,i).\omega_-(i,i')=\widehat\omega_+(i',i).(9)

For points p,qp,q with p1<q1p_1<q_1, their slope and supporting line height are the functions in (10); write he(x)=hPiPj(x)h_e(x)=h_{P_iP_j}(x) for an edge e=(i,j)e=(i,j). slope⁡(p,q)=q2−p2q1−p1,hpq(x)=p2+(x−p1)slope⁡(p,q).\operatorname{slope}(p,q)=\frac{q_2-p_2}{q_1-p_1},\qquad h_{pq}(x)=p_2+(x-p_1)\operatorname{slope}(p,q).(10) A convex cover of a drawing DD with label set II is an owner map c:E→Ic:E\to I such that every segment lies on or above every supporting line in its owner class✦; a concave cover has the reversed inequality.✦ Denote these sets of covers by Cov⁡cvx(D;I)\operatorname{Cov}_{\mathrm{cvx}}(D;I) and Cov⁡ccv(D;I)\operatorname{Cov}_{\mathrm{ccv}}(D;I), respectively, with the conditions in (11) applying whenever e,f∈Ee,f\in E, c(e)=c(f)c(e)=c(f) and z∈[Pf1,Pf2]z\in[P_{f_1},P_{f_2}]. c∈Cov⁡cvx(D;I):he(z1)≤z2,c∈Cov⁡ccv(D;I):z2≤he(z1).\begin{aligned} c\in\operatorname{Cov}_{\mathrm{cvx}}(D;I)&: &&h_e(z_1)\le z_2,\\ c\in\operatorname{Cov}_{\mathrm{ccv}}(D;I)&: &&z_2\le h_e(z_1). \end{aligned}(11)

The Claim

Theorem 1. Let 𝒮\mathcal S be a uniform exchange system with n,a>0n,a>0, and let DD be its exchange drawing. The convex and concave owners define covers: ω+∈Cov⁡cvx(D;J×In).\omega_+\in\operatorname{Cov}_{\mathrm{cvx}}(D;J\times I_n).(12)✦ ω−∈Cov⁡ccv(D;J×In).\omega_-\in\operatorname{Cov}_{\mathrm{ccv}}(D;J\times I_n).(13)✦ For every exchange edge e∈Ee\in E, the owners satisfy ω+(e)∈J×V.\omega_+(e)\in J\times V.(14)✦ ω−(e)∈J×V.\omega_-(e)\in J\times V.(15)✦ If PP is in general position, its abscissae are distinct, and DD has no triple edge intersections, then |𝒞(D)|≤2a2S2.|\mathcal C(D)|\le 2a^2S^2.(16)✦

In the paper, the result reads: for a consecutive window of batches of distance aa with SS distinct exchange endpoints, the exchange edges partition into at most aSaS convex polygonal chains and into at most aSaS concave polygonal chains, and have at most 2a2S22a^2S^2 properly crossing pairs.

What Is Checked

The cover statements (12) and (13), with the owner restrictions (14) and (15), are stated over uniform exchange systems with n,a>0n,a>0; the crossing bound (16) additionally assumes general position, distinct abscissae and no triple edge intersections. Every exchange edge admits an edge token trace.✦