The Setting
Vertex splitting replaces vertices by copies and assigns edges to those copies. The neighborhood reduction bound concerns the triangle mass retained when the copies have smaller neighborhood masses.
Let be a finite simple graph on with positive vertex weights . For a vertex of , the neighborhood is the set of vertices adjacent to .✦ For a finite simple graph on with vertex weights , vertices , and a set , the vertex mass , neighborhood mass , and common neighborhood mass are the sums of vertex weights over , , and , respectively, as in (1). (1)
The cross mass between vertex sets of is the sum of the products of endpoint weights over ordered adjacent pairs from to ; the sets may overlap. The unordered edge mass of is the sum of the products of endpoint weights over its edges, as in (2). (2)
For a finite simple graph with vertex weights and a vertex of , the twice neighborhood triangle mass is the sum of over neighbors of , and the unordered triangle mass is one sixth of the sum of over vertices of , as in (3). (3)
For a real parameter , the growth function on nonnegative arguments is defined by (4); logarithms are natural. (4)✦ A weighted graph with vertex weights satisfies the cross mass bound with constant if, for every real and all vertex sets of , the implication in (5) holds. (5)✦
The exceptional mass constant , entropy bound constant , smoothing bound constant , and splitting bound constant are defined by (6). (6) The loss ratio is the real-valued function of a real variable given in (7). (7)✦
An edge-injective graph projection from a simple graph on to is an adjacency-preserving map that is injective on directed edges: if and are directed edges of with , then .✦
The Claim
Theorem 1. Let be a finite simple graph with positive vertex weights satisfying the cross mass bound with . Suppose , , and for every vertex . There exist a finite simple graph on a vertex set and an edge-injective graph projection such that the weights satisfy (8). (8)✦
In the paper, the result reads: choose with ; if a finite positive-weighted graph satisfies the cross mass bound with and has every neighborhood mass at most , where , then there is a finite positive-weighted graph with a weight-preserving, adjacency-preserving map to injective on directed edges, every neighborhood mass at most , , the same cross mass bound, and .
What Is Checked
The neighborhood reduction bound is stated over finite simple graphs with strictly positive vertex weights satisfying (5), parameters and with , and a uniform neighborhood mass bound .