OctoInformBeta

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

Optimizer triangle bound: A uniform comparison with edge mass for each excluded clique size

Triangle mass at a graph potential maximum.

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 G=(V,E)G=(V,E) be a finite simple graph and let w:V→ℝw:V\to\mathbb R be a real vertex weight. The quantities at issue are the masses of edges and triangles when ww maximizes a graph potential.

The neighborhood NG(v)N_G(v) of a vertex v∈Vv\in V is the set of vertices adjacent to vv.✦ The vertex mass w(S)w(S) of a set S⊆VS\subseteq V is the sum of its vertex weights, as in (1). w(S)=∑v∈Sw(v).w(S)=\sum_{v\in S}w(v).(1)✦ The common neighborhood mass cw(u,v)c_w(u,v) of vertices u,v∈Vu,v\in V is the mass of their common neighborhood, given by (2). cw(u,v)=w(NG(u)∩NG(v)).c_w(u,v)=w\bigl(N_G(u)\cap N_G(v)\bigr).(2)✦

The cross edge mass ew(S,D)e_w(S,D) of vertex sets S,D⊆VS,D\subseteq V is the sum of endpoint weight products over ordered adjacent pairs from SS to DD, as in (3); the sets may overlap. ew(S,D)=∑u∈S∑v∈D∩NG(u)w(u)w(v).e_w(S,D)=\sum_{u\in S}\ \sum_{v\in D\cap N_G(u)}w(u)w(v).(3)✦ The unordered edge mass MG(w)M_G(w) of a vertex weight ww on GG is the sum of endpoint weight products over the edges of GG, with the normalization in (4). MG(w)=12ew(V,V)=∑{u,v}∈Ew(u)w(v).M_G(w)=\frac12 e_w(V,V)=\sum_{\{u,v\}\in E}w(u)w(v).(4)✦

The twice neighborhood triangle mass τw(u)\tau_w(u) at a vertex u∈Vu\in V is twice the sum of endpoint weight products over edges within NG(u)N_G(u); its expression in common neighborhood masses is (5). τw(u)=∑v∈NG(u)w(v)cw(u,v).\tau_w(u)=\sum_{v\in N_G(u)}w(v)c_w(u,v).(5)✦ The unordered triangle mass TG(w)T_G(w) of a vertex weight ww on GG is the sum of products of vertex weights over unordered triangles of GG, with the normalization in (6), where 𝒯(G)\mathcal T(G) denotes the set of three-element cliques of GG. TG(w)=16∑u∈Vw(u)τw(u)=∑Q∈𝒯(G)∏v∈Qw(v).T_G(w)=\frac16\sum_{u\in V}w(u)\tau_w(u) =\sum_{Q\in\mathcal T(G)}\prod_{v\in Q}w(v).(6)✦

The Potential and Its Maximizers

The vertex potential ϕ:ℝ→ℝ\phi:\mathbb R\to\mathbb R is the function defined by (7), with natural logarithms and the convention 0log⁡0=00\log 0=0. ϕ(t)={t(1−log⁡|t|),t≠0,0,t=0.\phi(t)= \begin{cases} t(1-\log|t|),&t\ne0,\\ 0,&t=0. \end{cases}(7) The graph potential FG(w)F_G(w) of a real vertex weight ww is the sum of its vertex potentials minus its unordered edge mass, as in (8). FG(w)=∑v∈Vϕ(w(v))−MG(w).F_G(w)=\sum_{v\in V}\phi(w(v))-M_G(w).(8)✦ An optimizer ww of FGF_G is a nonnegative vertex weight that is a global maximizer among all nonnegative vertex weights, as specified in (9). w(v)≥0(v∈V),FG(q)≤FG(w)for every q:V→[0,∞).w(v)\ge0\quad(v\in V),\qquad F_G(q)\le F_G(w)\quad \text{for every }q:V\to[0,\infty).(9)✦

The Claim

Theorem 1. Let r≥2r\ge2 be an integer, let GG be a finite KrK_r-free simple graph, and let ww be an optimizer of FGF_G. The bound (10) holds for a real constant Br>0B_r>0 depending only on rr. TG(w)≤BrMG(w).T_G(w)\le B_r M_G(w).(10)✦

In the paper, the result reads: every maximizer ww on a finite KrK_r-free graph satisfies TG(w)≤BrMG(w)T_G(w)\le B_rM_G(w), where C△C_{\triangle} is the paper’s triangle-bound function and Br=C△(16r2)B_r=C_{\triangle}(16r^2), and both masses are zero when the vertex set is empty.

What Is Checked

The claim is stated over nonnegative global maximizers of the potential (8) on finite KrK_r-free simple graphs, for integers r≥2r\ge2.