OctoInformBeta

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

Lemma 5.3: Neighborhood mass bounds through an edge-injective projection of a weighted graph

Vertex splitting with controlled triangle loss.

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

Consider splitting vertices of a positive weighted graph to reduce neighborhood mass while controlling the loss of triangle mass. Let GG be a finite simple graph on VV and let w:V→(0,∞)w:V\to(0,\infty) be a vertex weighting.

The neighborhood NG(u)N_G(u) of u∈Vu\in V is the set of vertices adjacent to uu.✦ For S⊆VS\subseteq V, the vertex mass w(S)w(S) is the sum of its vertex weights, as in (1). NG(u)={v∈V:uv∈E(G)},w(S)=∑v∈Sw(v).N_G(u)=\{v\in V:uv\in E(G)\}, \qquad w(S)=\sum_{v\in S}w(v).(1) The neighborhood mass sus_u at uu and the common neighborhood mass cuvc_{uv} of u,v∈Vu,v\in V are the vertex masses in (2). su=w(NG(u)),cuv=w(NG(u)∩NG(v)).s_u=w(N_G(u)), \qquad c_{uv}=w(N_G(u)\cap N_G(v)).(2)

For vertex sets S,D⊆VS,D\subseteq V, which may overlap, the cross edge mass ew(S,D)e_w(S,D) is the sum of endpoint weight products over ordered adjacent pairs from SS to DD, as in (3). ew(S,D)=∑u∈S∑v∈Duv∈E(G)w(u)w(v).e_w(S,D)=\sum_{u\in S}\ \sum_{\substack{v\in D\\uv\in E(G)}}w(u)w(v).(3)✦ For a real parameter tt, the growth function gt:[0,∞)→ℝg_t:[0,\infty)\to\mathbb R is defined by (4), where log\log denotes the natural logarithm. gt(s)={s(t+max⁡{0,log⁡(1/s)}),s>0,0,s=0.g_t(s)= \begin{cases} s\bigl(t+\max\{0,\log(1/s)\}\bigr),&s>0,\\ 0,&s=0. \end{cases}(4)✦ A weighting ww on GG satisfies the cross mass bound with real constant CC if, for every t≥1t\ge1 and S,D⊆VS,D\subseteq V with w(S),w(D)≤etw(S),w(D)\le e^t, (5) holds. ew(S,D)≤Cgt(w(S)).e_w(S,D)\le Cg_t(w(S)).(5)✦

The twice neighborhood triangle mass quq_u at u∈Vu\in V is twice the sum of endpoint weight products over edges inside NG(u)N_G(u)✦, and the unordered triangle mass TG(w)T_G(w) is the sum of vertex weight products over unordered triangles, as in (6). qu=∑v∈NG(u)w(v)cuv,TG(w)=16∑u∈Vw(u)qu.q_u=\sum_{v\in N_G(u)}w(v)c_{uv}, \qquad T_G(w)=\frac16\sum_{u\in V}w(u)q_u.(6)

Splitting Vertices

The oriented edges of GG are the ordered adjacent vertex pairs in E→(G)\vec E(G).✦ The tail map π:E→(G)→V\pi:\vec E(G)\to V sends each oriented edge to its first vertex, as in (7). E→(G)={(u,v)∈V2:uv∈E(G)},π(u,v)=u.\vec E(G)=\{(u,v)\in V^2:uv\in E(G)\}, \qquad \pi(u,v)=u.(7) The induced weighting w′w' on E→(G)\vec E(G) is defined by w′=w∘πw'=w\circ\pi.

An edge-injective graph projection ρ\rho from a simple graph JJ to GG is an adjacency-preserving map ρ:V(J)→V\rho:V(J)\to V that is injective on directed edges: if (a,b)(a,b) and (c,d)(c,d) are directed edges of JJ with (ρ(a),ρ(b))=(ρ(c),ρ(d))(\rho(a),\rho(b))=(\rho(c),\rho(d)), then (a,b)=(c,d)(a,b)=(c,d).✦

For a real parameter CC, define the exceptional mass constant KCK_C, the entropy bound constant ACA_C, the smoothing bound constant BCB_C, and the splitting constant aCa_C by (8). KC=42C2+2C,AC=10+KC,BC=2AC+1,aC=6(BC+AC+1).\begin{aligned} K_C&=42C^2+2C,& A_C&=10+K_C,\\ B_C&=2\sqrt{A_C+1},& a_C&=6(B_C+A_C+1). \end{aligned}(8)

The Claim

Theorem 1 (Weighted vertex splitting). Let GG be a finite simple graph on VV with at least one edge and let w:V→(0,∞)w:V\to(0,\infty) be a vertex weighting satisfying the cross mass bound (5) with C≥1C\ge1. Let x≥32x\ge32, and suppose that cuv≥1/xc_{uv}\ge1/x on every edge uv∈E(G)uv\in E(G) and su≤exs_u\le e^x at every vertex u∈Vu\in V. Then there is a simple graph HH on E→(G)\vec E(G) for which the tail map π\pi is an edge-injective graph projection to GG and whose induced weighting w′w' satisfies (9). ∑y∈NH(z)w′(y)≤ex(z∈E→(G)),TH(w′)≥(1−aClog⁡xx)TG(w).\begin{gathered} \sum_{y\in N_H(z)}w'(y)\le e^{\sqrt{x}} \qquad(z\in\vec E(G)),\\ T_H(w')\ge\left(1-a_C\frac{\log x}{\sqrt{x}}\right)T_G(w). \end{gathered}(9)✦

In the paper, the result reads: if GG is finite, ww is positive, C≥1C\ge1 and x≥32x\ge32, the cross mass bound (5) holds, cuv≥1/xc_{uv}\ge1/x on every edge, su≤exs_u\le e^x at every vertex and TG(w)>0T_G(w)>0, then there is a choice of labels producing a split graph H′H' with induced weights w′w' and a projection to GG that preserves vertex weights and maps directed edges injectively to directed edges, with every neighborhood weight at most exe^{\sqrt{x}} and TH′(w′)≥(1−aClog⁡x/x)TG(w)T_{H'}(w')\ge(1-a_C\log x/\sqrt{x})T_G(w), where aC=6(BC+AC+1)a_C=6(B_C+A_C+1).

What Is Checked

The claim is stated over finite positively weighted simple graphs with at least one edge and their oriented-edge sets, subject to the cross mass condition and the local mass bounds in the theorem.