OctoInformBeta

OpenAI preprint, September 2026 · Section 3. From cross mass to triangle mass

Theorem 3.1: A uniform bound for positive vertex weights on finite simple graphs

A cross-mass condition controls triangle 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 G=(V,E)G=(V,E) be a finite simple graph and let w:V→(0,∞)w:V\to(0,\infty) assign a positive weight to each vertex. The question is how a restriction on weighted adjacency between vertex sets constrains the total weight of triangles.

The vertex mass w(S)w(S) of a set S⊆VS\subseteq V is the sum of its vertex weights.✦ The cross mass ew(S,D)e_w(S,D) of two sets S,D⊆VS,D\subseteq V is the sum of endpoint weight products over ordered adjacent pairs from SS to DD, as in (1); the sets may overlap. w(S)=∑v∈Sw(v),ew(S,D)=∑u∈S,v∈D{u,v}∈Ew(u)w(v).\begin{aligned} w(S)&=\sum_{v\in S}w(v),\\ e_w(S,D)&=\sum_{\substack{u\in S,\ v\in D\\\{u,v\}\in E}}w(u)w(v). \end{aligned}(1)

The unordered edge mass MG(w)M_G(w) is the sum of endpoint weight products over unordered edges of GG, with the normalization in (2). MG(w)=∑{u,v}∈Ew(u)w(v)=12ew(V,V).M_G(w)=\sum_{\{u,v\}\in E}w(u)w(v)=\frac12 e_w(V,V).(2)✦

The neighborhood NG(u)N_G(u) of a vertex uu is the set of vertices adjacent to uu.✦ The common neighborhood mass mw(u,v)m_w(u,v) of vertices u,vu,v is the total weight of their common neighbors, as in (3). NG(u)={v∈V:{u,v}∈E},mw(u,v)=∑z∈NG(u)∩NG(v)w(z).N_G(u)=\{v\in V:\{u,v\}\in E\},\qquad m_w(u,v)=\sum_{z\in N_G(u)\cap N_G(v)}w(z).(3)

The twice neighborhood triangle mass τw(u)\tau_w(u) at uu is twice the sum of endpoint weight products over unordered edges contained in NG(u)N_G(u), given by (4). τw(u)=∑v∈NG(u)w(v)mw(u,v).\tau_w(u)=\sum_{v\in N_G(u)}w(v)m_w(u,v).(4)✦

The unordered triangle mass TG(w)T_G(w) is the sum of products of the three vertex weights over unordered triangles of GG, with the normalization in (5). TG(w)=16∑u∈Vw(u)τw(u).T_G(w)=\frac16\sum_{u\in V}w(u)\tau_w(u).(5)✦

For a real parameter xx, the growth function gx:[0,∞)→ℝg_x:[0,\infty)\to\mathbb R is the function defined in (6), where log\log is the natural logarithm. 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)✦

A positive vertex weight ww on GG satisfies the cross-mass bound with constant CC if (7) holds for every real x≥1x\ge1 and every pair of sets S,D⊆VS,D\subseteq V with w(S)≤exw(S)\le e^x and w(D)≤exw(D)\le e^x. ew(S,D)≤Cgx(w(S)).e_w(S,D)\le Cg_x\bigl(w(S)\bigr).(7)✦

The Claim

Theorem 1. Let C≥1C\ge1 be real. There is a constant B>0B>0, depending only on CC, such that every finite simple graph GG with positive vertex weights ww satisfying the cross-mass bound with constant CC obeys (8). TG(w)≤BMG(w).T_G(w)\le B M_G(w).(8)✦

In the paper, the result reads: for every C≥1C\ge1 there is a constant C△(C)C_{\triangle}(C) such that every finite simple graph GG with positive vertex weights ww satisfying the cross-mass bound with constant CC has TG(w)≤C△(C)MG(w)T_G(w)\le C_{\triangle}(C)M_G(w).

What Is Checked

The statement is over finite simple graphs with positive real vertex weights and the cross-mass bound of (7), using the edge mass of (2) and the triangle mass of (5).