OctoInformBeta

OpenAI preprint, September 2026 · Section 6. Recovering the two induced trees

Lemma 6.1 [One root per component; construction consequence]: For the directed network determined by paired transversals of the nonroot dual vertices

Two root edges preserve acyclicity.

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

Can two sides of a root triangle be adjoined to selected sides of the black triangles without creating a cycle? The setting is a cubic bipartite network and its dual triangulation.

Let NN be a network on a vertex set VV, and let DD be a network on a vertex set FF, with common edge set EE. A network NN on a vertex set VV with edge set EE is an assignment of a tail and a head in VV to every edge in EE.✦ The underlying simple graph graph⁡(N)\operatorname{graph}(N) of a network NN on VV is the simple graph on VV that joins distinct vertices whenever an edge of NN has those endpoints.✦ A simple network NN is a network with no loops in which each unordered endpoint pair determines at most one edge.✦ An edge ee of a network NN is incident with a vertex vv of NN when vv is the tail or head of ee✦; the star at vv in NN is the set of edges of NN incident with vv.✦

For a network NN, the oriented incidence matrix INI_N, boundary operator ∂N\partial_N on real edge weights ww, and gradient operator ∇N\nabla_N on real vertex potentials ff are 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,\qquad (\nabla_N f)(e)=f(\operatorname{head}_N(e))-f(\operatorname{tail}_N(e)). \end{aligned}(1) A cycle-cut duality (N,D)(N,D) is a pair of networks with a common edge set whose underlying graphs are connected and whose 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 on an edge set SS is a configuration of three distinct corners c(i)c(i) and three distinct edges a(i)a(i), indexed cyclically by i∈ℤ/3ℤi\in\mathbb Z/3\mathbb Z, where the edges exhaust SS and a(i)a(i) joins c(i)c(i) to c(i+1)c(i+1).✦ A colored triangulation duality (N,D)(N,D) is a cycle-cut duality in which NN and DD are simple, NN is cubic, and a black vertex class B⊆VB\subseteq V gives a bipartite coloring. For each v∈Vv\in V, there is a triangle of DD with edge set the star of vv in NN; write its corners and edges as cv(i)c_v(i) and av(i)a_v(i).

For an edge ee and a vertex uu of DD, the outgoing edge sign ϵD(e,u)\epsilon_D(e,u) is the sign +1+1 when uu is the tail of ee in DD, and −1-1 otherwise.✦ The triangles in a colored triangulation duality satisfy the orientation compatibility in (3), where 𝟏{v}\mathbf 1_{\{v\}} is the potential equal to one at vv and zero elsewhere. (∇N𝟏{v})(av(i))=ϵD(av(i),cv(i)).(\nabla_N\mathbf 1_{\{v\}})(a_v(i)) =\epsilon_D(a_v(i),c_v(i)).(3)

Corner Choices and Root Edges

Fix a root vertex t0∈Vt_0\in V and call its dual triangle the root triangle. The nonroot black triangles are indexed by AA, and the nonroot dual vertices form XX, as in (4). A=B\{t0},X=F\{ct0(0),ct0(1),ct0(2)}.A=B\setminus\{t_0\}, \qquad X=F\setminus\{c_{t_0}(0),c_{t_0}(1),c_{t_0}(2)\}.(4) A triangle system (ct)t∈A(c_t)_{t\in A} on FF is a family of injective corner maps ct:ℤ/3ℤ→Fc_t:\mathbb Z/3\mathbb Z\to F in which two triangles sharing two distinct corners have the same index.✦ The black face triangle system (ct)t∈A(c_t)_{t\in A} at t0t_0 is the triangle system on FF whose corner maps are those of the dual triangles indexed by t∈At\in A.✦

A state ss onto XX is a choice of one corner index s(t)s(t) for each t∈At\in A such that its selected vertex map vsv_s is a bijection onto XX, as specified in (5).✦ Such a state is a triangle transversal. vs(t)=ct(s(t)),vs:A→Xis bijective.v_s(t)=c_t(s(t)),\qquad v_s:A\longrightarrow X\ \text{is bijective}.(5) Paired states (r,s)(r,s) are an ordered pair of triangle transversals onto XX that are pointwise distinct: vr(t)≠vs(t)v_r(t)\ne v_s(t) for every t∈At\in A.✦ The opposite edge graph QsQ_s is the simple graph on FF whose edges are the sides opposite the choices of ss, given by (6). E(Qs)={{ct(i),ct(j)}:t∈A,i≠j,i≠s(t),j≠s(t)}.E(Q_s)= \bigl\{\{c_t(i),c_t(j)\}:t\in A,\ i\ne j,\ i\ne s(t),\ j\ne s(t)\bigr\}.(6)✦

The third corner index k(i,j)=−(i+j)k(i,j)=-(i+j), calculated modulo three, is the remaining index when i≠ji\ne j, and their common index when i=ji=j.✦ For paired states (r,s)(r,s), the third corner network Q→r,s\vec Q_{r,s} is the network on FF with edge set AA and endpoints given by (7). tail⁡Q→r,s(t)=vr(t),head⁡Q→r,s(t)=ct(k(r(t),s(t))).\operatorname{tail}_{\vec Q_{r,s}}(t)=v_r(t), \qquad \operatorname{head}_{\vec Q_{r,s}}(t)=c_t(k(r(t),s(t))).(7)✦

The two-edge sink extension of a network QQ on FF, with starting vertices b0,b1b_0,b_1 and target zz, is the network on FF that retains the edges of QQ and adjoins two distinct edges b0→zb_0\to z and b1→zb_1\to z.✦ For a root index ii, the consecutive starting indices are i+ji+j for j=0,1j=0,1.✦ For paired states (r,s)(r,s) and a root index ii, the root-augmented network Qˆr,s,i\widehat Q_{r,s,i} is the network on FF obtained from Q→r,s\vec Q_{r,s} by adjoining the two edges specified by (8); all corner indices are taken modulo three. tail⁡Qˆr,s,i(j)=ct0(i+j),head⁡Qˆr,s,i(j)=ct0(i+2)(j=0,1).\operatorname{tail}_{\widehat Q_{r,s,i}}(j)=c_{t_0}(i+j), \qquad \operatorname{head}_{\widehat Q_{r,s,i}}(j)=c_{t_0}(i+2) \quad(j=0,1).(8)✦

The Claim

Theorem 1. Let (r,s)(r,s) be paired states onto XX, and suppose that QsQ_s is a forest. For every root index i∈ℤ/3ℤi\in\mathbb Z/3\mathbb Z, graph⁡(Qˆr,s,i)is acyclic.\operatorname{graph}(\widehat Q_{r,s,i})\ \text{is acyclic}.(9)✦

In the paper, the result reads: for a pair (r,s)(r,s) with QsQ_s a forest, every component of QsQ_s contains exactly one of the three root corners.

What Is Checked

The statement (9) is over a colored triangulation duality, its black face triangle system at t0t_0, paired transversals of the nonroot dual vertices XX, and a root index ii, under the hypothesis that QsQ_s is a forest. The boundary and gradient operators are linear.