OctoInformBeta

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

Proposition 5.4: Positive vertex weights and a cross mass bound control the cost of splitting

A triangle mass bound under neighborhood reduction.

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

Vertex splitting replaces vertices by copies and assigns edges to those copies. The neighborhood reduction bound concerns the triangle mass retained when the copies have smaller neighborhood masses.

Let GG be a finite simple graph on VV with positive vertex weights ww. For a vertex uu of GG, the neighborhood NG(u)N_G(u) is the set of vertices adjacent to uu.✦ For a finite simple graph GG on VV with vertex weights ww, vertices u,v∈Vu,v\in V, and a set S⊆VS\subseteq V, the vertex mass w(S)w(S), neighborhood mass w(NG(u))w(N_G(u)), and common neighborhood mass cG(u,v)c_G(u,v) are the sums of vertex weights over SS, NG(u)N_G(u), and NG(u)∩NG(v)N_G(u)\cap N_G(v), respectively, as in (1). w(S)=∑v∈Sw(v),w(NG(u))=∑v∈NG(u)w(v),cG(u,v)=∑z∈NG(u)∩NG(v)w(z).\begin{aligned} w(S)&=\sum_{v\in S}w(v), & w(N_G(u))&=\sum_{v\in N_G(u)}w(v),\\ c_G(u,v)&=\sum_{z\in N_G(u)\cap N_G(v)}w(z). \end{aligned}(1)

The cross mass ew(S,D)e_w(S,D) between vertex sets S,DS,D of GG is the sum of the products of endpoint weights over ordered adjacent pairs from SS to DD; the sets may overlap. The unordered edge mass MG(w)M_G(w) of GG is the sum of the products of endpoint weights over its edges, as in (2). ew(S,D)=∑u∈S∑v∈Duv∈E(G)w(u)w(v),MG(w)=12ew(V,V).e_w(S,D)=\sum_{u\in S}\ \sum_{\substack{v\in D\\uv\in E(G)}}w(u)w(v), \qquad M_G(w)=\frac12 e_w(V,V).(2)

For a finite simple graph GG with vertex weights ww and a vertex uu of GG, the twice neighborhood triangle mass qG(u)q_G(u) is the sum of w(v)cG(u,v)w(v)c_G(u,v) over neighbors vv of uu, and the unordered triangle mass TG(w)T_G(w) is one sixth of the sum of w(u)qG(u)w(u)q_G(u) over vertices uu of GG, as in (3). qG(u)=∑v∈NG(u)w(v)cG(u,v),TG(w)=16∑u∈Vw(u)qG(u).q_G(u)=\sum_{v\in N_G(u)}w(v)c_G(u,v), \qquad T_G(w)=\frac16\sum_{u\in V}w(u)q_G(u).(3)

For a real parameter tt, the growth function gtg_t on nonnegative arguments is defined by (4); logarithms are natural. 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 weighted graph GG with vertex weights ww satisfies the cross mass bound with constant CC if, for every real t≥1t\ge1 and all vertex sets S,DS,D of GG, the implication in (5) holds. w(S)≤etandw(D)≤et⇒ew(S,D)≤Cgt(w(S)).w(S)\le e^t\ \text{and}\ w(D)\le e^t \quad\Longrightarrow\quad e_w(S,D)\le Cg_t(w(S)).(5)✦

The exceptional mass constant ηC\eta_C, entropy bound constant βC\beta_C, smoothing bound constant σC\sigma_C, and splitting bound constant aCa_C are defined by (6). ηC=42C2+2C,βC=10+ηC,σC=2βC+1,aC=6(σC+βC+1).\begin{aligned} \eta_C&=42C^2+2C,&\qquad \beta_C&=10+\eta_C,\\ \sigma_C&=2\sqrt{\beta_C+1},& a_C&=6(\sigma_C+\beta_C+1). \end{aligned}(6) The loss ratio ℓ\ell is the real-valued function of a real variable xx given in (7). ℓ(x)=log⁡xx.\ell(x)=\frac{\log x}{\sqrt{x}}.(7)✦

An edge-injective graph projection π:U→V\pi:U\to V from a simple graph JJ on UU to GG is an adjacency-preserving map 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))(\pi(a),\pi(b))=(\pi(c),\pi(d)), then (a,b)=(c,d)(a,b)=(c,d).✦

The Claim

Theorem 1. Let GG be a finite simple graph with positive vertex weights ww satisfying the cross mass bound with C≥1C\ge1. Suppose x≥32x\ge32, aCℓ(x)≤1a_C\ell(x)\le1, and w(NG(u))≤exw(N_G(u))\le e^x for every vertex uu. There exist a finite simple graph JJ on a vertex set UU and an edge-injective graph projection π:U→V(G)\pi:U\to V(G) such that the weights w′=w∘πw'=w\circ\pi satisfy (8). w′(NJ(a))≤exfor every a∈U,TJ(w′)≥(1−aCℓ(x))TG(w)−MG(w)x.\begin{aligned} w'(N_J(a))&\le e^{\sqrt{x}}&&\text{for every }a\in U,\\ T_J(w')&\ge\bigl(1-a_C\ell(x)\bigr)T_G(w)-\frac{M_G(w)}{x}. \end{aligned}(8)✦

In the paper, the result reads: choose X(C)≥32X(C)\ge32 with 2aClog⁡X(C)/X(C)≤1/22a_C\log X(C)/\sqrt{X(C)}\le1/2; if a finite positive-weighted graph GG satisfies the cross mass bound with C≥1C\ge1 and has every neighborhood mass at most exe^x, where x>X(C)x>X(C), then there is a finite positive-weighted graph (G′,w′)(G',w') with a weight-preserving, adjacency-preserving map to (G,w)(G,w) injective on directed edges, every neighborhood mass at most exe^{\sqrt{x}}, TG′(w′)≥(1−aClog⁡x/x)TG(w)−MG(w)/xT_{G'}(w')\ge(1-a_C\log x/\sqrt{x})T_G(w)-M_G(w)/x, the same cross mass bound, and MG′(w′)≤MG(w)M_{G'}(w')\le M_G(w).

What Is Checked

The neighborhood reduction bound is stated over finite simple graphs with strictly positive vertex weights satisfying (5), parameters C≥1C\ge1 and x≥32x\ge32 with aCℓ(x)≤1a_C\ell(x)\le1, and a uniform neighborhood mass bound w(NG(u))≤exw(N_G(u))\le e^x.