The Setting
The problem is to find a large independent set in a clique-free graph from a bound on its maximum degree and a uniform weighted triangle estimate. Let be a finite simple graph with vertices. Its independence number is the maximum cardinality of an independent set in . The neighborhood of is the set of vertices adjacent to .✦
For a real vertex weight , the vertex mass of and the cross edge mass between are the sums in (1); the latter runs over ordered adjacent pairs, and may overlap. (1) The unordered edge mass is the sum of endpoint weight products over the unordered edges of , given by (2). (2)✦
The common neighborhood mass of vertices is the mass of their common neighbors.✦ The twice neighborhood triangle mass at is the sum over its neighbors in (3). (3) The unordered triangle mass is the sum of products of the three vertex weights over unordered triangles of , given by (4). (4)✦
The Variational Functional
The vertex potential is the real-valued function of a real variable given by (5). All logarithms are natural, with the convention . (5) The weighted graph potential is the sum of the vertex potentials minus the unordered edge mass, as in (6). (6)✦ An optimizer of is a nonnegative weight such that for every nonnegative weight .✦ Write for the scalar optimal value of on nonnegative weights.
The Claim
Theorem 1. Fix an integer and real numbers and . Assume that every finite -free graph and every optimizer of satisfy the uniform estimate (7): (7) Let be a finite -free graph on vertices with maximum degree at most , and put . There exists an independent set for which (8) holds: (8)✦ The independence number satisfies (9): (9)✦
In the paper, the result reads: for every integer , every real , and every finite -free graph with vertices and maximum degree at most , and , where is the uniform optimizer triangle constant and .
What Is Checked
The statements concern finite -free simple graphs with the stated maximum degree bound, together with the weighted masses and nonnegative global maximizers of the variational functional appearing in the uniform hypothesis (7).