OctoInformBeta

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

Lemma 3.3: Local triangle identities and neighborhood bounds for weighted finite simple graphs

Edge peeling with controlled triangle loss.

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

Lemma 3.3 concerns the triangle mass retained when edges with small common neighborhood mass are deleted. Let GG be a finite simple graph on vertex set VV, with edge set E(G)E(G), and let w:V→ℝw:V\to\mathbb R be a vertex weight, written wu=w(u)w_u=w(u). The neighborhood NG(u)N_G(u) of u∈Vu\in V is the set of vertices adjacent to uu.✦

The vertex mass w(S)w(S) of a set S⊆VS\subseteq V is the sum of its vertex weights.✦ The cross mass ewG(S,D)e_w^G(S,D) of 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)=∑u∈Swu,ewG(S,D)=∑u∈S∑v∈Duv∈E(G)wuwv.w(S)=\sum_{u\in S}w_u, \qquad e_w^G(S,D)=\sum_{u\in S}\sum_{\substack{v\in D\\uv\in E(G)}}w_uw_v.(1) An unordered triangle of GG is a three-element set of pairwise adjacent vertices; write 𝒦3(G)\mathcal K_3(G) for the set of these triangles. 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 edges and triangles, respectively, in (2). MG(w)=12ewG(V,V)=∑{u,v}∈E(G)wuwv,TG(w)=∑{u,v,z}∈𝒦3(G)wuwvwz.M_G(w)=\frac12 e_w^G(V,V) =\sum_{\{u,v\}\in E(G)}w_uw_v, \qquad T_G(w)=\sum_{\{u,v,z\}\in\mathcal K_3(G)}w_uw_vw_z.(2)

The neighborhood mass sG(u)s_G(u) is the vertex mass of NG(u)N_G(u)✦, and the common neighborhood mass cG(u,v)c_G(u,v) is the vertex mass of NG(u)∩NG(v)N_G(u)\cap N_G(v).✦ The local triangle quantity hG(u)h_G(u) is twice the unordered edge mass inside NG(u)N_G(u), with the formulas in (3). sG(u)=w(NG(u)),cG(u,v)=w(NG(u)∩NG(v)),hG(u)=∑v∈NG(u)wvcG(u,v)=2∑{v,z}∈E(G)v,z∈NG(u)wvwz.\begin{aligned} s_G(u)&=w(N_G(u)), &c_G(u,v)&=w(N_G(u)\cap N_G(v)),\\ h_G(u)&=\sum_{v\in N_G(u)}w_vc_G(u,v) =2\sum_{\substack{\{v,z\}\in E(G)\\v,z\in N_G(u)}}w_vw_z. \end{aligned}(3) The same notation with HH in place of GG refers to masses computed in a spanning subgraph HH with the same vertex weights.

An oriented edge (u,v)(u,v) of GG is an ordered pair of adjacent vertices, with tail uu and head vv; write ℰG→\mathcal E_G^{\to} for their set. An ordered triangle t=(t1,t2,t3)t=(t_1,t_2,t_3) of GG is a triple of pairwise adjacent vertices, whose first, second and third vertices are t1,t2,t3t_1,t_2,t_3, respectively; write 𝒯G→\mathcal T_G^{\to} for their set. The weight ωw(t)\omega_w(t) of an ordered triangle tt is the product in (4). ωw(t)=wt1wt2wt3.\omega_w(t)=w_{t_1}w_{t_2}w_{t_3}.(4)✦

The Claim

Theorem 1. For a finite simple graph GG with real vertex weights, the normalization identities are (5) and (6). 6TG(w)=∑u∈VwuhG(u).6T_G(w)=\sum_{u\in V}w_uh_G(u).(5)✦ ∑t∈𝒯G→ωw(t)=6TG(w).\sum_{t\in\mathcal T_G^{\to}}\omega_w(t)=6T_G(w).(6)✦ For every function f:V×V→ℝf:V\times V\to\mathbb R, the edge marginal is (7). ∑t∈𝒯G→ωw(t)f(t1,t2)=∑(u,v)∈ℰG→wuwvcG(u,v)f(u,v).\sum_{t\in\mathcal T_G^{\to}}\omega_w(t)f(t_1,t_2) =\sum_{(u,v)\in\mathcal E_G^{\to}}w_uw_vc_G(u,v)f(u,v).(7)✦

Suppose wu≥0w_u\ge0 for every vertex and sG(u)≤Ls_G(u)\le L for every vertex, where L∈ℝL\in\mathbb R. Then (8) holds. TG(w)≤L3MG(w).T_G(w)\le\frac{L}{3}M_G(w).(8)✦

Assume wu>0w_u>0 for every vertex and τ>0\tau>0. There is a spanning subgraph H⊆GH\subseteq G satisfying (9). cH(u,v)≥τfor every uv∈E(H),TH(w)≥TG(w)−τMG(w).\begin{gathered} c_H(u,v)\ge\tau\qquad\text{for every }uv\in E(H),\\ T_H(w)\ge T_G(w)-\tau M_G(w). \end{gathered}(9)✦

Let τ∈ℝ\tau\in\mathbb R, and assume wu≥0w_u\ge0 for every vertex, with cG(u,v)≥τc_G(u,v)\ge\tau on every edge of GG. Every nonisolated vertex uu satisfies (10). sG(u)≥τ.s_G(u)\ge\tau.(10)✦ For every vertex uu, (11) holds. hG(u)≥τsG(u).h_G(u)\ge\tau s_G(u).(11)✦

In the paper, the result reads: for a positive-weighted finite simple graph GG, with sG(u)=w(NG(u))s_G(u)=w(N_G(u)), cG(u,v)=w(NG(u)∩NG(v))c_G(u,v)=w(N_G(u)\cap N_G(v)) and hG(u)=∑v∈NG(u)wvcG(u,v)h_G(u)=\sum_{v\in N_G(u)}w_vc_G(u,v), one has ∑{u,v}∈E(G)wuwvcG(u,v)=3TG(w)\sum_{\{u,v\}\in E(G)}w_uw_vc_G(u,v)=3T_G(w) and ∑u∈VwuhG(u)=6TG(w)\sum_{u\in V}w_uh_G(u)=6T_G(w); if every neighborhood has mass at most LL, then TG(w)≤(L/3)MG(w)T_G(w)\le(L/3)M_G(w); for every τ>0\tau>0, successive edge deletions give a spanning subgraph G′G' with cG′(u,v)≥τc_{G'}(u,v)\ge\tau on each retained edge and TG′(w)≥TG(w)−τMG(w)T_{G'}(w)\ge T_G(w)-\tau M_G(w), every nonisolated vertex uu of G′G' has sG′(u)≥τs_{G'}(u)\ge\tau and hG′(u)≥τsG′(u)h_{G'}(u)\ge\tau s_{G'}(u), and a cross-mass bound on GG passes to G′G' with the same constant.

What Is Checked

The statements concern finite simple graphs with real vertex weights, arbitrary real test functions on ordered vertex pairs in (7), and spanning subgraphs on the same vertex set in (9).