OctoInformBeta

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

Lemma 2.2: Bounded multipliers preserve mean vertex weights on a chosen induced subgraph

Clique exclusion permits sparse random rescaling.

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 A⊆VA\subseteq V. Random rescaling replaces a vertex weight wvw_v by wvmvw_vm_v, where mvm_v is a random multiplier. The question concerns the expected edge mass under bounds on the multipliers and prescribed coordinate means.

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∈Swv.w(S)=\sum_{v\in S}w_v.(1)✦ The cross edge 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); the sets may overlap. ew(S,D)=∑u∈S∑v∈Duv∈Ewuwv.e_w(S,D)=\sum_{u\in S}\sum_{\substack{v\in D\\uv\in E}}w_uw_v.(2)✦ The unordered edge mass MG(w)M_G(w) is the sum of endpoint weight products over unordered edges, as in (3). MG(w)=∑{u,v}∈Ewuwv=12ew(V,V).M_G(w)=\sum_{\{u,v\}\in E}w_uw_v=\frac12 e_w(V,V).(3)✦

Finite Random Multipliers

A finite real lottery LL on a set XX is a finite sequence ((pi,xi))i=1N((p_i,x_i))_{i=1}^N of outcomes xi∈Xx_i\in X with real weights pip_i.✦ The expectation 𝔼Lf\mathbb E_L f of a real function ff on XX and the total weight τ(L)\tau(L) of the lottery are defined by (4). 𝔼Lf=∑i=1Npif(xi),τ(L)=𝔼L1=∑i=1Npi.\mathbb E_L f=\sum_{i=1}^N p_i f(x_i), \qquad \tau(L)=\mathbb E_L 1=\sum_{i=1}^N p_i.(4) A lottery LL is nonnegative if every listed weight pip_i is nonnegative✦; it is a probability lottery if it is nonnegative and τ(L)=1\tau(L)=1.✦

A lottery LL of multiplier functions m:V→ℝm:V\to\mathbb R is bounded by bb and supported on AA if every listed multiplier satisfies (5). 0≤mv≤b(v∈V),mv=0(v∉A).0\le m_v\le b\quad(v\in V), \qquad m_v=0\quad(v\notin A).(5)✦ For a multiplier lottery L=((pi,m(i)))i=1NL=((p_i,m^{(i)}))_{i=1}^N, the expected edge mass of the rescaled weights is defined by (6), where (wm)v=wvmv(wm)_v=w_vm_v. 𝔼LMG(wm)=∑i=1NpiMG(wm(i)).\mathbb E_L M_G(wm)=\sum_{i=1}^N p_i M_G(wm^{(i)}).(6)✦ For a nonnegative integer kk and a real parameter ε\varepsilon, the multiplier bound bk+2(ε)b_{k+2}(\varepsilon) is the number in (7). bk+2(ε)=2(k+2)kεk.b_{k+2}(\varepsilon)=\frac{2^{(k+2)k}}{\varepsilon^k}.(7)✦

The Claim

Theorem 1. Let kk be a nonnegative integer, let GG be a finite simple graph with strictly positive vertex weights ww, and let A⊆VA\subseteq V induce a Kk+2K_{k+2}-free graph. For 0<ε≤120<\varepsilon\le\tfrac12, there is a probability lottery LL of multiplier functions, bounded by bk+2(ε)b_{k+2}(\varepsilon) and supported on AA, satisfying (8). 𝔼Lmv={1,v∈A,0,v∉A,(v∈V),𝔼LMG(wm)≤εw(A)2.\mathbb E_L m_v= \begin{cases} 1,&v\in A,\\ 0,&v\notin A, \end{cases} \quad(v\in V), \qquad \mathbb E_L M_G(wm)\le\varepsilon\,w(A)^2.(8)✦

In the paper, the result reads: for an integer r≥2r\ge2, a finite KrK_r-free graph GG with positive vertex weights ww and s=w(V)s=w(V), and 0<ε≤120<\varepsilon\le\tfrac12, there are jointly distributed multipliers (mv)v∈V(m_v)_{v\in V} with finite joint support such that 0≤mv≤br(ε)=2r(r−2)ε−(r−2)0\le m_v\le b_r(\varepsilon)=2^{r(r-2)}\varepsilon^{-(r-2)}, 𝔼mv=1\mathbb E m_v=1 for every v∈Vv\in V, and 𝔼MG(wm)≤εs2\mathbb E M_G(wm)\le\varepsilon s^2.

What Is Checked

The claim is stated over finite simple graphs with positive real vertex weights, vertex subsets whose induced graphs are Kk+2K_{k+2}-free, and finite probability lotteries of real multiplier functions.