The Setting
Consider splitting vertices of a positive weighted graph to reduce neighborhood mass while controlling the loss of triangle mass. Let be a finite simple graph on and let be a vertex weighting.
The neighborhood of is the set of vertices adjacent to .✦ For , the vertex mass is the sum of its vertex weights, as in (1). (1) The neighborhood mass at and the common neighborhood mass of are the vertex masses in (2). (2)
For vertex sets , which may overlap, the cross edge mass is the sum of endpoint weight products over ordered adjacent pairs from to , as in (3). (3)✦ For a real parameter , the growth function is defined by (4), where denotes the natural logarithm. (4)✦ A weighting on satisfies the cross mass bound with real constant if, for every and with , (5) holds. (5)✦
The twice neighborhood triangle mass at is twice the sum of endpoint weight products over edges inside ✦, and the unordered triangle mass is the sum of vertex weight products over unordered triangles, as in (6). (6)
Splitting Vertices
The oriented edges of are the ordered adjacent vertex pairs in .✦ The tail map sends each oriented edge to its first vertex, as in (7). (7) The induced weighting on is defined by .
An edge-injective graph projection from a simple graph to is an adjacency-preserving map that is injective on directed edges: if and are directed edges of with , then .✦
For a real parameter , define the exceptional mass constant , the entropy bound constant , the smoothing bound constant , and the splitting constant by (8). (8)
The Claim
Theorem 1 (Weighted vertex splitting). Let be a finite simple graph on with at least one edge and let be a vertex weighting satisfying the cross mass bound (5) with . Let , and suppose that on every edge and at every vertex . Then there is a simple graph on for which the tail map is an edge-injective graph projection to and whose induced weighting satisfies (9). (9)✦
In the paper, the result reads: if is finite, is positive, and , the cross mass bound (5) holds, on every edge, at every vertex and , then there is a choice of labels producing a split graph with induced weights and a projection to that preserves vertex weights and maps directed edges injectively to directed edges, with every neighborhood weight at most and , where .
What Is Checked
The claim is stated over finite positively weighted simple graphs with at least one edge and their oriented-edge sets, subject to the cross mass condition and the local mass bounds in the theorem.