OctoInformBeta

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

Iteration in the proof of Theorem 3.1: A cross mass hypothesis and a small loss threshold control the ratio of triangle mass to edge mass

Weighted triangle bounds at finite squaring scales.

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 GG be a finite simple graph on VV, with a nonnegative real vertex weighting ww. How large can its weighted triangle count be relative to its weighted edge count when all weights are positive and masses between vertex sets obey a uniform bound?

The vertex mass w(A)w(A) of a set A⊆VA\subseteq V is its total weight✦, and the neighborhood NG(u)N_G(u) of a vertex u∈Vu\in V is the set of vertices adjacent to uu, as in (1). w(A)=∑v∈Aw(v),NG(u)={v∈V:uv∈E(G)}.w(A)=\sum_{v\in A}w(v), \qquad N_G(u)=\{v\in V:uv\in E(G)\}.(1) The neighborhood mass w(NG(u))w(N_G(u)) of a vertex u∈Vu\in V is the total weight of its neighborhood.

The cross mass ew(A,B)e_w(A,B) of two vertex sets is the sum of endpoint weight products over ordered adjacent pairs in A×BA\times B, given by (2); the sets AA and BB may overlap. ew(A,B)=∑u∈A∑v∈Buv∈E(G)w(u)w(v).e_w(A,B)=\sum_{u\in A}\ \sum_{\substack{v\in B\\uv\in E(G)}}w(u)w(v).(2)✦

The common neighborhood mass cw(u,v)c_w(u,v) of vertices u,v∈Vu,v\in V is the total weight of the vertices adjacent to both uu and vv.✦ For a vertex u∈Vu\in V, the number τw(u)\tau_w(u) is twice the weighted edge count inside NG(u)N_G(u), as in (3). cw(u,v)=w(NG(u)∩NG(v)),τw(u)=∑v∈NG(u)w(v)cw(u,v).c_w(u,v)=w\bigl(N_G(u)\cap N_G(v)\bigr), \qquad \tau_w(u)=\sum_{v\in N_G(u)}w(v)c_w(u,v).(3)

The unordered edge mass MG(w)M_G(w) and unordered triangle mass TG(w)T_G(w) are the sums of vertex weight products over unordered edges and unordered triangles, respectively; their expressions in terms of the local masses are (4). MG(w)=ew(V,V)2,TG(w)=16∑u∈Vw(u)τw(u).M_G(w)=\frac{e_w(V,V)}2, \qquad T_G(w)=\frac16\sum_{u\in V}w(u)\tau_w(u).(4)

Cross Mass and Numerical Scales

For a real parameter xx, the growth function gxg_x on nonnegative real numbers is defined by (5). gx(s)={s(x+max⁡{0,log⁡(1/s)}),s>0,0,s=0.g_x(s)= \begin{cases} s\bigl(x+\max\{0,\log(1/s)\}\bigr),&s>0,\\ 0,&s=0. \end{cases}(5)✦ A weighted graph (G,w)(G,w) satisfies the cross mass bound with real constant CC if, for every x≥1x\ge1 and every pair of vertex sets A,BA,B with w(A),w(B)≤exw(A),w(B)\le e^x, the inequality (6) holds. ew(A,B)≤Cgx(w(A)).e_w(A,B)\le Cg_x\bigl(w(A)\bigr).(6)✦

The exceptional mass constant b(C)b(C) and entropy bound constant h(C)h(C) are real functions of CC, as are the smoothing bound constant s(C)s(C) and splitting constant σ(C)\sigma(C); they are defined by (7). b(C)=42C2+2C,h(C)=10+b(C),s(C)=2h(C)+1,σ(C)=6(s(C)+h(C)+1).\begin{aligned} b(C)&=42C^2+2C,& h(C)&=10+b(C),\\ s(C)&=2\sqrt{h(C)+1},& \sigma(C)&=6\bigl(s(C)+h(C)+1\bigr). \end{aligned}(7)

For a real number xx, the loss ratio ℓ(x)\ell(x) is the natural logarithm of xx divided by its square root, as in (8). ℓ(x)=log⁡xx.\ell(x)=\frac{\log x}{\sqrt{x}}.(8) For a real base XX, the squaring scales xn(X)x_n(X) form the sequence defined by (9), with nn a nonnegative integer. x0(X)=X,xn+1(X)=xn(X)2.x_0(X)=X, \qquad x_{n+1}(X)=x_n(X)^2.(9)✦

The Claim

Theorem 1. For every real number aa, there is a real number XX such that X≥32,aℓ(X)≤14.X\ge32, \qquad a\ell(X)\le\frac14.(10)✦

Let C≥1C\ge1 and X≥32X\ge32 satisfy σ(C)ℓ(X)≤1/4\sigma(C)\ell(X)\le1/4, and let nn be a nonnegative integer. Let GG be a finite simple graph with strictly positive real vertex weights ww satisfying the cross mass bound with constant CC. Suppose that w(NG(u))≤exn(X)w(N_G(u))\le e^{x_n(X)} for every vertex uu. Then TG(w)≤(1+eX3)(2−2−n)MG(w).T_G(w)\le \left(1+\frac{e^X}{3}\right)\left(2-2^{-n}\right)M_G(w).(11)✦

In the paper, the result reads: iterating x↦xx\mapsto\sqrt{x} down to a threshold X(C)X(C) makes the cumulative relative triangle loss at most 1/21/2 and the cumulative edge mass charge at most MG(w)M_G(w), and the terminal neighborhood bound yields TG(w)≤2(1+eX(C)/3)MG(w)T_G(w)\le2(1+e^{X(C)}/3)M_G(w).

What Is Checked

The assertions (10) and (11) concern, respectively, arbitrary real coefficients and finite simple graphs with strictly positive real vertex weights satisfying the cross mass and neighborhood mass hypotheses at the stated numerical parameters.