The Setting
Let be a finite simple graph on , with a nonnegative real vertex weighting . How large can its weighted triangle count be relative to its weighted edge count when all weights are positive and masses between vertex sets obey a uniform bound?
The vertex mass of a set is its total weight✦, and the neighborhood of a vertex is the set of vertices adjacent to , as in (1). (1) The neighborhood mass of a vertex is the total weight of its neighborhood.
The cross mass of two vertex sets is the sum of endpoint weight products over ordered adjacent pairs in , given by (2); the sets and may overlap. (2)✦
The common neighborhood mass of vertices is the total weight of the vertices adjacent to both and .✦ For a vertex , the number is twice the weighted edge count inside , as in (3). (3)
The unordered edge mass and unordered triangle mass are the sums of vertex weight products over unordered edges and unordered triangles, respectively; their expressions in terms of the local masses are (4). (4)
Cross Mass and Numerical Scales
For a real parameter , the growth function on nonnegative real numbers is defined by (5). (5)✦ A weighted graph satisfies the cross mass bound with real constant if, for every and every pair of vertex sets with , the inequality (6) holds. (6)✦
The exceptional mass constant and entropy bound constant are real functions of , as are the smoothing bound constant and splitting constant ; they are defined by (7). (7)
For a real number , the loss ratio is the natural logarithm of divided by its square root, as in (8). (8) For a real base , the squaring scales form the sequence defined by (9), with a nonnegative integer. (9)✦
The Claim
Theorem 1. For every real number , there is a real number such that (10)✦
Let and satisfy , and let be a nonnegative integer. Let be a finite simple graph with strictly positive real vertex weights satisfying the cross mass bound with constant . Suppose that for every vertex . Then (11)✦
In the paper, the result reads: iterating down to a threshold makes the cumulative relative triangle loss at most and the cumulative edge mass charge at most , and the terminal neighborhood bound yields .
What Is Checked
The assertions (10) and (11) concern, respectively, arbitrary real coefficients and finite simple graphs with strictly positive real vertex weights satisfying the cross mass and neighborhood mass hypotheses at the stated numerical parameters.