OctoInformBeta

OpenAI preprint, September 2026 · Section 5. Splitting vertices and bounding triangle mass

Admissible labels and the splitting graph: A tail-preserving assignment determines the retained edges and a splitting constant

Splitting vertices by admissible incidence labels.

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 vertex splitting redistributes the edges incident to a vertex among labelled copies of that vertex. Let G=(V,E)G=(V,E) be a finite simple graph. The set of oriented edges of GG is E→(G)={(u,v)∈V×V:uv∈E}.\vec E(G)=\{(u,v)\in V\times V:uv\in E\}.(1)✦ For an oriented edge e=(u,v)e=(u,v) of GG in (1), the tail s(e)s(e) and head t(e)t(e) are given by s(e)=us(e)=u and t(e)=vt(e)=v, respectively. For an oriented edge e=(u,v)e=(u,v) of GG, the reverse edge e‾\bar e is the oriented edge given by e‾=(v,u)\bar e=(v,u).✦

The set E→(G)\vec E(G) also supplies the copy labels: (u,y)(u,y) labels a copy of uu. A tail-preserving incidence assignment FF for GG is a map F:E→(G)→E→(G)F:\vec E(G)\to\vec E(G) satisfying (2). s(F(e))=s(e)for every e∈E→(G).s(F(e))=s(e)\qquad\text{for every }e\in\vec E(G).(2) Fix a subset 𝒜⊆E→(G)\mathcal A\subseteq\vec E(G) of admissible incidences.

For a real parameter CC, the exceptional mass constant DCD_C is the real number given by (3). DC=42C2+2C.D_C=42C^2+2C.(3)✦ The entropy bound constant ACA_C and the smoothing bound constant BCB_C are the real numbers given by (4). AC=10+DC,BC=2AC+1.A_C=10+D_C,\qquad B_C=2\sqrt{A_C+1}.(4)

The Definition

Definition 1. Let FF be a tail-preserving incidence assignment for GG, and let 𝒜⊆E→(G)\mathcal A\subseteq\vec E(G) be a set of admissible incidences. The admissible splitting graph H=H(G,F,𝒜)H=H(G,F,\mathcal A) is the graph on E→(G)\vec E(G) whose adjacency relation is given by (5). a∼Hb⇔∃e∈E→(G)(e∈𝒜∧e‾∈𝒜∧F(e)=a∧F(e‾)=b).a\sim_H b \quad\Longleftrightarrow\quad \exists e\in\vec E(G)\; \bigl(e\in\mathcal A\ \land\ \bar e\in\mathcal A\ \land\ F(e)=a\ \land\ F(\bar e)=b\bigr).(5)✦ For a real parameter CC, the splitting constant aCa_C is the real number given by (6). aC=6(BC+AC+1).a_C=6(B_C+A_C+1).(6)✦

In the paper, the result reads: use the common-time kernels KuK_u supplied by Lemma 4.1 and jointly sample all their rows; for vertex weights wvw_v and a parameter xx, call a label yy at incidence (u,v)(u,v) admissible when Ku(y,v)≥wve−xK_u(y,v)\ge w_v e^{-\sqrt{x}}, group the neighbors with the same admissible label at uu into Au,yA_{u,y}, create a copy (u,y)(u,y) of weight wuw_u for every nonempty group, retain an edge uvuv between its assigned copies when both incidence labels are admissible, and put aC=6(BC+AC+1)a_C=6(B_C+A_C+1).

What Is Checked

The construction is stated over a finite simple graph GG, a tail-preserving map FF of its oriented edges, an arbitrary admissibility set 𝒜\mathcal A, and a real parameter CC. The adjacency relation in (5) is symmetric and loopless.