OctoInformBeta

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

Lemma 3.2: Edge and neighborhood masses decrease for inherited nonnegative weights

Cross mass bounds survive edge projections.

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

An edge map between finite simple graphs may identify vertices while keeping distinct ordered adjacent pairs distinct. The question is how weighted adjacency sums change when vertices inherit the weights of their images.

Let GG and HH be finite simple graphs on vertex sets VV and UU, respectively. For real vertex weights w:V→ℝw:V\to\mathbb R on GG, the vertex mass w(S)w(S) of a set S⊆VS\subseteq V and the cross edge mass ew(S,D)e_w(S,D) of two possibly overlapping sets S,D⊆VS,D\subseteq V are the sums in (1) and (2), respectively: w(S)=∑v∈Swv.w(S)=\sum_{v\in S}w_v.(1)✦ ew(S,D)=∑u∈S,v∈Duv∈E(G)wuwv.e_w(S,D)=\sum_{\substack{u\in S,\ v\in D\\uv\in E(G)}}w_uw_v.(2)✦

For real vertex weights ww on a finite simple graph GG, the unordered edge mass MG(w)M_G(w) is the sum in (3): MG(w)=12ew(V,V)=∑{u,v}∈E(G)wuwv.M_G(w)=\frac12 e_w(V,V)=\sum_{\{u,v\}\in E(G)}w_uw_v.(3) The neighborhood NG(v)N_G(v) of a vertex vv of GG is the set of vertices of GG adjacent to vv; its neighborhood mass is (4). w(NG(v))=∑u∈NG(v)wu.w(N_G(v))=\sum_{u\in N_G(v)}w_u.(4)✦

For a real parameter xx, the growth function gxg_x on nonnegative arguments is (5), with log\log denoting 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}(5)✦ A graph GG with real vertex weights ww satisfies the cross mass bound with real constant CC if (6) holds for every real x≥1x\geq1 and sets S,D⊆VS,D\subseteq V with w(S),w(D)≤exw(S),w(D)\leq e^x: ew(S,D)≤Cgx(w(S)).e_w(S,D)\leq Cg_x(w(S)).(6)

An edge-injective graph projection from HH to GG is a map π:U→V\pi:U\to V that sends adjacent vertices to adjacent vertices and is injective on ordered adjacent pairs.✦ The inherited weight w̃\widetilde w on HH is the vertex weight in (7). w̃a=wπ(a)(a∈U).\widetilde w_a=w_{\pi(a)}\qquad(a\in U).(7)

The Claim

Theorem 1. Let π:U→V\pi:U\to V be an edge-injective graph projection from HH to GG, and let ww be nonnegative vertex weights on GG, with inherited weights w̃\widetilde w on HH. The edge mass bound is (8), and the neighborhood mass bound (9) holds for every a∈Ua\in U: MH(w̃)≤MG(w).M_H(\widetilde w)\leq M_G(w).(8)✦ w̃(NH(a))≤w(NG(π(a))).\widetilde w(N_H(a))\leq w(N_G(\pi(a))).(9)✦

Suppose also that C≥0C\geq0 and (G,w)(G,w) satisfies the cross mass bound with constant CC. Then (10) holds for every x≥1x\geq1 and A,B⊆UA,B\subseteq U with w̃(A),w̃(B)≤ex\widetilde w(A),\widetilde w(B)\leq e^x: ew̃(A,B)≤Cgx(w̃(A)).e_{\widetilde w}(A,B)\leq Cg_x(\widetilde w(A)).(10)✦

In the paper, the result reads: if a positive-weighted finite simple graph (G,w)(G,w) satisfies the cross mass bound with constant CC, then every finite simple graph HH with an edge-injective graph projection π:U→V\pi:U\to V and inherited weights w̃\widetilde w satisfies the same cross mass bound and, writing TT for unordered triangle mass, satisfies MH(w̃)≤MG(w)M_H(\widetilde w)\leq M_G(w), TH(w̃)≤TG(w)T_H(\widetilde w)\leq T_G(w), and w̃(NH(a))≤w(NG(π(a)))\widetilde w(N_H(a))\leq w(N_G(\pi(a))) for every a∈Ua\in U, and these conclusions persist under finite compositions of such maps.

What Is Checked

The statements are over finite simple graphs and edge-injective graph projections with inherited nonnegative real vertex weights; the cross mass assertion also assumes a nonnegative constant and the cross mass bound on the target graph.