OctoInformBeta

OpenAI preprint, September 2026 · Section 3. Two disjoint states

Proposition 3.1 [Existence of a pair]: An incidence capacity bound for the black triangles away from a root

Two disjoint states from cut conditions.

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

The question is whether two selections of corners in black triangles can differ in every triangle while each covers every vertex outside a root triangle exactly once.

A network NN on finite vertex and edge sets VV and EE is a directed multigraph assigning a tail and a head to each edge.✦ Let DD be a second network, with vertex set FF and the same edge set EE. The underlying simple graph of a network joins distinct vertices when they are endpoints of an edge.✦ A network is simple when it has no loops and no two edges have the same unordered pair of endpoints.✦ An edge is incident to a vertex v∈Vv\in V when vv is its tail or head; the star st⁡N(v)\operatorname{st}_N(v) is the set of edges incident to vv.

The oriented incidence matrix INI_N has rows indexed by VV and columns indexed by EE. The boundary operator ∂N\partial_N sends real edge weights ww to their signed net inflows, and the gradient operator ∇N\nabla_N sends real vertex potentials ff to edge weights, with their values given by (1). IN(v,e)=𝟏{head⁡N(e)=v}−𝟏{tail⁡N(e)=v},∂Nw=INw,(∇Nf)(e)=f(head⁡N(e))−f(tail⁡N(e)).\begin{aligned} I_N(v,e)&=\mathbf{1}_{\{\operatorname{head}_N(e)=v\}} -\mathbf{1}_{\{\operatorname{tail}_N(e)=v\}},\\ \partial_N w&=I_Nw,\\ (\nabla_N f)(e)&=f(\operatorname{head}_N(e))-f(\operatorname{tail}_N(e)). \end{aligned}(1)

A cycle cut duality between NN and DD means that their underlying graphs are connected and their real cycle and cut spaces satisfy (2). ker⁡∂N=im⁡∇D,ker⁡∂D=im⁡∇N.\ker\partial_N=\operatorname{im}\nabla_D, \qquad \ker\partial_D=\operatorname{im}\nabla_N.(2)✦

A triangle TT in DD on an edge set HH is a configuration of three distinct corners cic_i and three distinct edges eie_i whose set is HH, with eie_i joining cic_i to ci+1c_{i+1}; indices are taken modulo three.✦ A colored triangulation duality between networks NN and DD is a cycle cut duality between them in which NN is simple and cubic and DD is simple, together with a black vertex class B⊆VB\subseteq V containing exactly one endpoint of each edge, and a triangle TvT_v in DD on st⁡N(v)\operatorname{st}_N(v) for each v∈Vv\in V. Write ci(v)c_i(v) and ei(v)e_i(v) for its corners and sides. For an edge ee and a vertex xx of DD, the outgoing edge sign σD(e,x)\sigma_D(e,x) is +1+1 when xx is the tail of ee in DD, and −1-1 otherwise.✦ The triangles satisfy the orientation compatibility condition (3). (∇N𝟏{v})(ei(v))=σD(ei(v),ci(v))(v∈V,i∈ℤ/3ℤ).(\nabla_N\mathbf{1}_{\{v\}})(e_i(v)) =\sigma_D(e_i(v),c_i(v)) \qquad(v\in V,\ i\in\mathbb{Z}/3\mathbb{Z}).(3)

Fix a black vertex v0v_0 and its root triangle t0=Tv0t_0=T_{v_0}. The other black triangles are indexed by AA, and XX is the set of dual vertices outside the root corners, as in (4). A=B\{v0},X=F\{c0(v0),c1(v0),c2(v0)}.A=B\setminus\{v_0\}, \qquad X=F\setminus\{c_0(v_0),c_1(v_0),c_2(v_0)\}.(4)

States and Cut Conditions

A triangle system on FF indexed by AA is a family of injective corner maps ct:ℤ/3ℤ→Fc_t:\mathbb{Z}/3\mathbb{Z}\to F in which a pair of distinct vertices belongs to at most one triangle.✦ For the black triangles indexed by AA, write Ct={c0(t),c1(t),c2(t)}C_t=\{c_0(t),c_1(t),c_2(t)\} for the corner set of TtT_t.

A state ss on XX is a choice of one corner in each triangle whose selected vertices give a bijection from AA to XX.✦ Write s(t)s(t) for the selected vertex of triangle tt, and 𝒮(X)\mathcal{S}(X) for the set of states in (5). 𝒮(X)={s:A→∼X∣s(t)∈Ct for every t∈A}.\mathcal{S}(X)= \{s:A\xrightarrow{\sim}X\mid s(t)\in C_t\text{ for every }t\in A\}.(5)✦ Two states r,sr,s on XX are partners, or disjoint states, when r(t)≠s(t)r(t)\ne s(t) for every t∈At\in A.✦ A pair (r,s)(r,s) on XX is an ordered pair of partner states on XX; let 𝒫(X)\mathcal{P}(X) be the set of pairs.✦

The edge cut δN(U)\delta_N(U) of a vertex set U⊆VU\subseteq V is the set of edges with exactly one endpoint in UU.✦ The network NN is three-edge-connected when every nonempty proper vertex set has an edge cut of size at least three.✦ The three-edge cuts of NN are trivial when every vertex set with an edge cut of size three is a singleton or has a singleton complement.✦

The Claim

Theorem 1. Let NN and DD have a colored triangulation duality, and let t0t_0 be a black root triangle. Suppose that NN is three-edge-connected and that all its three-edge cuts are trivial. For every S⊆XS\subseteq X, 2|S|≤∑t∈Amin⁡{2,|S∩Ct|}.2|S|\leq\sum_{t\in A}\min\{2,|S\cap C_t|\}.(6)✦ Moreover, 𝒫(X)≠⌀.\mathcal{P}(X)\ne\varnothing.(7)✦

What Is Checked

The capacity bound (6) and the existence statement (7) are stated over a finite colored triangulation duality with a black root and the two cut conditions on NN. The corner maps of the black triangles indexed by AA form a triangle system.✦