OctoInformBeta

OpenAI preprint, September 2026 · Section 2. An extremal weight and its cross-mass bound

Lemma 2.3: Overlapping vertex sets are allowed, with constant 16r216r^2 for KrK_r-free graphs and integers r≥2r\ge2

Clique-free optimizers have bounded cross mass.

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 with vertex set VV and edge set E(G)E(G). The question is how maximizing a graph potential restricts the weighted edges between two vertex sets.

For a real vertex weight w:V→ℝw:V\to\mathbb R, the vertex mass w(S)w(S) of a set S⊆VS\subseteq V is the sum in (1). w(S)=∑v∈Sw(v).w(S)=\sum_{v\in S}w(v).(1)✦ The cross mass ew(S,D)e_w(S,D) of vertex sets S,D⊆VS,D\subseteq V is the sum over ordered adjacent pairs in (2). 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).(2) The unordered edge mass MG(w)M_G(w) of a real vertex weight ww on GG is the sum of endpoint weight products over unordered edges of GG, as in (3). MG(w)=∑{u,v}∈E(G)w(u)w(v)=12ew(V,V).M_G(w)=\sum_{\{u,v\}\in E(G)}w(u)w(v)=\frac12e_w(V,V).(3)✦

The vertex potential φ:ℝ→ℝ\varphi:\mathbb R\to\mathbb R is the function in (4), with natural logarithms and the convention 0log⁡0=00\log0=0. φ(t)={t(1−log⁡|t|),t≠0,0,t=0.\varphi(t)= \begin{cases} t(1-\log|t|),&t\ne0,\\ 0,&t=0. \end{cases}(4)✦ 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 (5). FG(w)=∑v∈Vφ(w(v))−MG(w).F_G(w)=\sum_{v\in V}\varphi(w(v))-M_G(w).(5)✦ An optimizer ww for GG is a nonnegative vertex weight whose graph potential is at least that of every nonnegative vertex weight on GG.✦

For a real parameter xx, the growth function gx:[0,∞)→ℝg_x:[0,\infty)\to\mathbb R is defined by (6). 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}(6)✦ For a real vertex weight w:V→ℝw:V\to\mathbb R on GG, a cross-mass bound with real constant CC is the estimate ew(S,D)≤Cgx(w(S))e_w(S,D)\le Cg_x(w(S)) for every real x≥1x\ge1 and all vertex sets S,DS,D satisfying w(S),w(D)≤exw(S),w(D)\le e^x.

The Claim

Theorem 1. Let kk be a nonnegative integer, let GG be a finite simple Kk+2K_{k+2}-free graph, and let ww be an optimizer for GG. For every real x≥1x\ge1 and all vertex sets S,DS,D with w(S),w(D)≤exw(S),w(D)\le e^x, the cross-mass bound (7) holds. ew(S,D)≤16(k+2)2gx(w(S)).e_w(S,D)\le16(k+2)^2g_x(w(S)).(7)✦

In the paper, the result reads: if r≥2r\ge2 is an integer and ww maximizes FGF_G on a nonempty finite KrK_r-free graph GG, then for every x≥1x\ge1 and vertex sets S,DS,D with w(S),w(D)≤exw(S),w(D)\le e^x, one has ew(S,D)≤Crgx(w(S))e_w(S,D)\le C_rg_x(w(S)), where Cr=16r2C_r=16r^2, and the sets may overlap.

What Is Checked

The statement is over finite simple Kk+2K_{k+2}-free graphs with nonnegative integral kk, weights maximizing the graph potential among all nonnegative weights, and arbitrary vertex sets.