The Setting
Lemma 3.3 concerns the triangle mass retained when edges with small common neighborhood mass are deleted. Let be a finite simple graph on vertex set , with edge set , and let be a vertex weight, written . The neighborhood of is the set of vertices adjacent to .✦
The vertex mass of a set is the sum of its vertex weights.✦ The cross mass of sets is the sum of endpoint weight products over ordered adjacent pairs from to , as in (1); the sets may overlap.✦ (1) An unordered triangle of is a three-element set of pairwise adjacent vertices; write for the set of these triangles. The unordered edge mass and unordered triangle mass are the sums of vertex weight products over edges and triangles, respectively, in (2). (2)
The neighborhood mass is the vertex mass of ✦, and the common neighborhood mass is the vertex mass of .✦ The local triangle quantity is twice the unordered edge mass inside , with the formulas in (3). (3) The same notation with in place of refers to masses computed in a spanning subgraph with the same vertex weights.
An oriented edge of is an ordered pair of adjacent vertices, with tail and head ; write for their set. An ordered triangle of is a triple of pairwise adjacent vertices, whose first, second and third vertices are , respectively; write for their set. The weight of an ordered triangle is the product in (4). (4)✦
The Claim
Theorem 1. For a finite simple graph with real vertex weights, the normalization identities are (5) and (6). (5)✦ (6)✦ For every function , the edge marginal is (7). (7)✦
Suppose for every vertex and for every vertex, where . Then (8) holds. (8)✦
Assume for every vertex and . There is a spanning subgraph satisfying (9). (9)✦
Let , and assume for every vertex, with on every edge of . Every nonisolated vertex satisfies (10). (10)✦ For every vertex , (11) holds. (11)✦
In the paper, the result reads: for a positive-weighted finite simple graph , with , and , one has and ; if every neighborhood has mass at most , then ; for every , successive edge deletions give a spanning subgraph with on each retained edge and , every nonisolated vertex of has and , and a cross-mass bound on passes to 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).