OctoInformBeta

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

Lemma 6.2 [The selected set is a forest]: Corner-compatible matchings at a black root, and recovery from paired states with an acyclic opposite edge graph

Forest criteria for selected dual sides.

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 NN be a finite cubic network on VV and DD its dual triangulation on FF, with shared edge set EE. A directed network HH is a network with a specified tail and head for each edge.✦ The underlying simple graph G(N)G(N) of the network NN is the graph on VV joining distinct vertices when an edge of NN has those endpoints.✦ A simple network HH is a network with no loops and at most one edge with any given unordered pair of endpoints.✦ For a vertex v∈Vv\in V, the star star⁡N(v)\operatorname{star}_N(v) of vv in NN is the set of edges incident to vv✦; incidence means that vv is either endpoint.✦

For a network HH with vertex set VHV_H, its oriented incidence matrix BHB_H, boundary operator ∂H\partial_H and gradient operator ∇H\nabla_H are given by (1), for a real edge weighting zz and vertex potential ff: BH(v,e)=𝟏{head⁡H(e)=v}−𝟏{tail⁡H(e)=v},∂Hz=BHz,(∇Hf)(e)=f(head⁡H(e))−f(tail⁡H(e)).\begin{aligned} B_H(v,e)&=\mathbf 1_{\{\operatorname{head}_H(e)=v\}} -\mathbf 1_{\{\operatorname{tail}_H(e)=v\}},\\ \partial_H z&=B_Hz, & (\nabla_H f)(e)&=f(\operatorname{head}_H(e))-f(\operatorname{tail}_H(e)). \end{aligned}(1) A cycle-cut duality between NN and DD means that both 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 colored triangulation duality between NN and DD is a cycle-cut duality with NN simple and cubic, DD simple, and a black class B⊆VB\subseteq V containing exactly one endpoint of every edge. The triangles indexed by V\BV\setminus B are white. Each t∈Vt\in V has a dual triangle whose distinct corners ct(i)c_t(i) and distinct sides et(i)e_t(i) are cyclically indexed by i∈ℤ/3ℤi\in\mathbb Z/3\mathbb Z. The side et(i)e_t(i) joins ct(i)c_t(i) to ct(i+1)c_t(i+1), and the three sides are exactly star⁡N(t)\operatorname{star}_N(t). For an edge e∈Ee\in E and a vertex x∈Fx\in F of DD, the outgoing sign αD(e,x)\alpha_D(e,x) is the sign +1+1 if xx is the tail of ee in DD, and −1-1 otherwise.✦ The triangles satisfy the orientation compatibility (3): (∇N𝟏{t})(et(i))=αD(et(i),ct(i)).(\nabla_N\mathbf 1_{\{t\}})(e_t(i)) =\alpha_D(e_t(i),c_t(i)).(3) For distinct indices j,kj,k, write dt(j,k)d_t(j,k) for the side joining ct(j)c_t(j) to ct(k)c_t(k); it is et(j)e_t(j) when k=j+1k=j+1, and et(k)e_t(k) otherwise.✦

Fix a root triangle t0∈Vt_0\in V. The nonroot black triangles AA and the dual vertices XX outside the corners of the root triangle t0t_0 are the sets 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 three-corner maps indexed by AA in which two triangles sharing two distinct corners have the same index.✦ The black triangles indexed by AA form a triangle system with corner maps ctc_t.✦

States and Selected Networks

A state ss of the black triangle system is a choice of a corner index js(t)j_s(t) for each t∈At\in A such that its selected-corner map in (5) is a bijection onto XX: s(t)=ct(js(t)),s:A→Xis bijective.s(t)=c_t(j_s(t)), \qquad s:A\longrightarrow X\ \text{is bijective}.(5) A paired state (r,s)(r,s) is an ordered pair of states with r(t)≠s(t)r(t)\ne s(t) for every t∈At\in A.✦ The opposite edge graph QsQ_s is the simple graph on FF consisting of the sides of the black triangles opposite their selected corners s(t)s(t).✦

For corner indices j,kj,k, the third index h(j,k)h(j,k) is their negative sum modulo three; when j≠kj\ne k, it is the remaining index.✦ For a paired state (r,s)(r,s) and a triangle t∈At\in A, the first-to-third side qr,s(t)q_{r,s}(t) of tt is the side specified in (6): h(j,k)=−(j+k),qr,s(t)=dt(jr(t),h(jr(t),js(t))).h(j,k)=-(j+k), \qquad q_{r,s}(t)=d_t\bigl(j_r(t),h(j_r(t),j_s(t))\bigr).(6) For a root index ii, the root-augmented side labelling λr,s,i\lambda_{r,s,i} is the map from A⊔{0,1}A\sqcup\{0,1\} to EE in (7); its image is the removed edge set Rr,s,iR_{r,s,i}: λr,s,i(t)=qr,s(t)(t∈A),λr,s,i(j)=dt0(i+j,i+2)(j∈{0,1}),Rr,s,i=im⁡λr,s,i.\begin{aligned} \lambda_{r,s,i}(t)&=q_{r,s}(t) &&(t\in A),\\ \lambda_{r,s,i}(j)&=d_{t_0}(i+j,i+2) &&(j\in\{0,1\}),\\ R_{r,s,i}&=\operatorname{im}\lambda_{r,s,i}. \end{aligned}(7) All root corner indices in (7) are taken modulo three. The consecutive root corner indices based at ii are ii and i+1i+1, taken modulo three.

A perfect matching PP of NN is an edge set meeting each vertex star exactly once. Write ℳ(N)\mathcal M(N) for the family defined in (8), and mP(v)m_P(v) for the unique matching edge incident to vv when P∈ℳ(N)P\in\mathcal M(N): ℳ(N)={P⊆E:|P∩star⁡N(v)|=1 for every v∈V}.\mathcal M(N)= \bigl\{P\subseteq E:\ |P\cap\operatorname{star}_N(v)|=1 \text{ for every }v\in V\bigr\}.(8) For an edge e∈Ee\in E and a vertex x∈Fx\in F of DD, the opposite-end map oD(e,x)o_D(e,x) is head⁡D(e)\operatorname{head}_D(e) when x=tail⁡D(e)x=\operatorname{tail}_D(e), and tail⁡D(e)\operatorname{tail}_D(e) otherwise.✦ For a state ss and P∈ℳ(N)P\in\mathcal M(N), the selected corner network 𝒮s,P\mathcal S_{s,P} is the directed network on FF with edge set AA and endpoints prescribed by (9): tail⁡𝒮s,P(t)=s(t),head⁡𝒮s,P(t)=oD(mP(t),s(t)).\operatorname{tail}_{\mathcal S_{s,P}}(t)=s(t), \qquad \operatorname{head}_{\mathcal S_{s,P}}(t)=o_D(m_P(t),s(t)).(9)✦ A perfect matching PP of NN is compatible with a state ss of the black triangle system when the incidence condition (10) holds: s(t)∈{tail⁡D(mP(t)),head⁡D(mP(t))}(t∈A).s(t)\in\{\operatorname{tail}_D(m_P(t)), \operatorname{head}_D(m_P(t))\} \qquad(t\in A).(10)

For a map j:K→Ej:K\to E, the edge restriction of DD along jj is the directed network on FF with edge set KK in which each edge kk has the endpoints of j(k)j(k) in DD.✦ When jj is the inclusion of an edge subset PP, write this restriction as D[P]D[P].

The Claim

Theorem 1. Let NN and DD have the colored triangulation duality described above. For a state ss and a perfect matching PP compatible with ss, G(𝒮s,P)is a forest.G(\mathcal S_{s,P})\ \text{is a forest}.(11)✦ If, in addition, the root t0t_0 is black and its matching edge is the prescribed side mP(t0)=et0(i)m_P(t_0)=e_{t_0}(i), then G(D[P])is a forest.G(D[P])\ \text{is a forest}.(12)✦ For a black root t0t_0, a paired state (r,s)(r,s) with QsQ_s a forest, and any root index ii, there is a perfect matching as in (13): ∃S∈ℳ(N)S⊆E\Rr,s,i.\exists\,S\in\mathcal M(N)\qquad S\subseteq E\setminus R_{r,s,i}.(13)✦

In the paper, the result reads: if DD has no separating triangle, choose a pair (r,s)(r,s) with QsQ_s a forest, form the tree on white triangles by the complementary incidence-spoke construction, root it across the prescribed outer edge e0e_0, and select one edge at each black and white triangle as in Section 6, including e0e_0; the resulting selected set PP is a forest.

What Is Checked

Statements (11) and (12) concern finite colored cycle-cut dualities, states and perfect matchings satisfying (10), with a black root and prescribed root matching side for (12); statement (13) concerns the removed edge sets of paired states at a black root with QsQ_s a forest.