A logarithmic independence bound for clique-free graphs

1 Introduction

An independent set in a graph is a set of pairwise nonadjacent vertices. For a finite simple graph G, write \alpha(G) for the largest size of an independent set. If G has n>0 vertices, its average degree is d(G)=2|E(G)|/n. The graph is K_r-free if no r vertices are pairwise adjacent; throughout, exclusion means exclusion as an ordinary subgraph. All logarithms are natural. For general graphs, the elementary bound \alpha(G)\ge n/(d+1) is best possible, as disjoint unions of cliques show. Excluding a fixed clique forces larger independent sets. We prove that the improvement is a factor of order \log d.

The constant is uniform in both the number of vertices and the average degree. The theorem gives a positive answer to the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi, also recorded as Erdős Problem 802. The order n\log d/d is best possible up to a constant factor even for triangle-free graphs, and hence for the larger class of K_r-free graphs [1, pp. 314–315]. We do not optimize the constant c_r.

1.1 History and related results

Ajtai, Komlós and Szemerédi [2] proved the logarithmic improvement when triangles are excluded. Shearer [14] subsequently obtained the asymptotic coefficient 1: triangle-free graphs of average degree d\to\infty have independent sets of size at least (1-o(1))n\log d/d. In 1981, Ajtai, Erdős, Komlós and Szemerédi conjectured the same order of growth for each fixed forbidden clique [1, p. 314, Equation (3)]. They proved the lower bound \Omega_r(n\log\log d/d) as d\to\infty, so excluding any fixed clique already improves on the general bound. Shearer [15, Corollary 2] improved this to \Omega_r(n\log d/(d\log\log d)), again in terms of the average degree. Theorem 1.1 removes this remaining \log\log d denominator.

Subsequent refinements describe more of the graph’s local structure. Dutta, Mubayi and Subramanian [10] give bounds involving the full degree sequence. Davies, Kang, Pirot and Sereni [7, Theorem 30 and Corollary 31] develop a local-occupancy framework that improves constants and also gives coloring estimates. Dhawan [8, Theorems 1.3 and 1.4] allows bounded numbers of cliques, either globally or inside neighborhoods. For a fixed forbidden clique, these estimates retain a \log\log loss in the relevant degree parameter; they provide information beyond the uniform order sought in Theorem 1.1.

Several stronger local assumptions yield logarithmic bounds. Alon [3, Theorem 1.1 and the remark following its proof] treated graphs whose neighborhoods have bounded chromatic number, obtaining an average-degree bound of the required order. His argument also admits bounded fractional chromatic number in each neighborhood. Davies [6, Theorems 1 and 3] establishes weighted local versions: he bounds individual vertex inclusion probabilities in a random independent set under bounded neighborhood maximum average degree or fractional chromatic number. For every fixed three-colorable forbidden graph, Dhawan, Janzer and Methuku [9, Theorems 1.4 and 1.6] prove (1-o(1))n\log d/d as d\to\infty, uniformly in n. This attains leading coefficient 1 in that restricted class. Neither bounded neighborhood fractional chromatic number nor exclusion of a fixed three-colorable graph covers all ordinary K_r-free graphs for r\ge4. For the latter restriction, complete tripartite graphs illustrate the difference: they are K_4-free and contain every fixed three-colorable graph once their parts are large enough.

For comparison, let r(s,t) be the least integer N such that every N-vertex graph contains a K_s or an independent set of size t. The fixed off-diagonal Ramsey estimates in [12, Theorem 1.1] and [13, Theorem 1.1] determine logarithmic exponents for r(5,t) and, respectively, for r(s,t) with each fixed s\ge6. Together they state

These are estimates for extremal graph orders as t\to\infty. Theorem 1.1 controls every input graph using its own average degree, including graphs whose degree is small relative to their order. Neither companion is an input to the proof. In particular, the weighted triangle theorem used here is proved from its own cross-mass hypothesis.

1.2 The proof in outline

The proof uses positive vertex weights. For such a vector w, write w(S)=\sum_{v\in S}w_v, and define its edge and triangle masses by

Both sums are over unordered sets. The central step is to show that T_G(w) is at most a constant depending only on r times M_G(w) when w maximizes, over nonnegative vertex weights,

The zero-coordinate convention is 0\log0=0. Three stages establish the theorem.

1. 1.

   Extract a bound that survives changes to the graph. Section 2 chooses a maximizing weight and uses random multipliers of mean one to control the directed edge mass between any two vertex sets. The multiplier construction is recursive on the excluded clique size. Section 3 shows that this cross-mass bound survives edge deletion and splitting a vertex into copies carrying its original weight, provided each original edge is retained at most once.

2. 2.

   Reduce weighted neighborhoods without losing many triangles. Sections 4 and 5 prove a triangle bound for every weighted graph with that cross-mass property. At each reduction step, we first delete edges whose common neighborhoods have small weight, charging the lost triangle mass to their edge mass. For each vertex u, walks inside N(u) assign a probability distribution on N(u) to each starting vertex v\in N(u). The cross-mass bound limits the average entropy growth of these walks. At a suitable common time, the distributions started at v and z are close on average over ordered triangles (u,v,z), weighted by w_uw_vw_z.

   Sampling these distributions together groups the incident edges at u; close distributions usually give the same group to the two edges of a triangle. A cutoff on reversed transition probabilities bounds each group’s total neighbor weight; the entropy and density bounds, together with reversibility, control the average triangle mass discarded by the cutoff. Splitting vertices according to the resulting groups reduces the largest neighborhood weight from e^x to e^{\sqrt{x}}. The losses are summable through all iterations. Once every neighborhood has bounded weight, triangle mass is directly bounded by edge mass.

3. 3.

   Choose independent vertices at controlled cost. For a graph with maximum degree at most \Delta\ge3, evaluating F_G at the constant weight (\log\Delta)/\Delta gives an extremal value at least a constant multiple of n(\log\Delta)^2/\Delta. When we delete a closed neighborhood and retain the old maximizing weights elsewhere, edges between the chosen vertex’s neighbors contribute to the cost. Averaging over the chosen vertex with probabilities proportional to its weight counts these edges as triangles. Section 6 uses the triangle bound to find a vertex whose closed-neighborhood deletion reduces this value by at most D_r\log\Delta. Selecting such a vertex and repeating on the remaining graph gives an independent set of size at least a constant multiple of n\log\Delta/\Delta. The same degree bound \Delta is kept throughout this induction. Deleting the original graph’s high-degree vertices then yields the average-degree bound in Theorem 1.1.

The weighted triangle theorem is a separate statement about cross masses; it has no clique hypothesis. Preservation of the cross-mass bound under vertex splitting permits repeated reduction without requiring the new weights to remain maximizers. The entropy estimate controls only averages over a specified triangle distribution, and the splitting argument uses exactly those averages. Every threshold in these two steps depends only on the cross-mass constant. The proof gives an existence result with an r-dependent constant; it makes no claim of an efficient algorithm or an optimal leading constant.

2 An extremal weight and its cross-mass bound

We first choose vertex weights for which a variational inequality controls the mass of edges between two sets. Clique exclusion enters through a random modification that keeps every weight unchanged in expectation while making the expected edge mass small.

For a finite simple graph G and a real vector a=(a_v)_{v\in V(G)}, put

Thus this quadratic expression is defined even when some coordinates are negative. For nonnegative weights w, write w(S)=\sum_{v\in S}w_v and

This is a directed cross mass: an edge with both ends in S\cap D is counted twice. All logarithms are natural, and 0\log 0=0.

2.1 The extremal weight

The functional below is the unit-parameter specialization of the entropy-minus-edge potential used by Davies [6, Section 3.3, proof of Theorem 17]. We give its elementary maximizing properties here.

Define

The maximum in this definition exists, as the following lemma shows.

For the empty graph on no vertices we set F_G^*=0; no positive-coordinate assertion is needed in that case.

2.2 Random multipliers with small expected edge mass

The recursive use of clique-free neighborhoods goes back to the sparse-subgraph argument of Ajtai, Erdős, Komlós and Szemerédi [1, Section 3]. Here the recursion preserves each vertex weight in expectation. The next lemma applies to arbitrary positive weights and does not require the maximizing equations.

The construction successively removes neighborhoods from the remaining induced graph, until every remaining vertex has small neighborhood weight. Each removed part excludes a smaller clique, and the remainder has small edge mass. We then retain one part at random and divide its weights by that part’s selection probability. Every vertex keeps its original expected weight, while edges joining different parts disappear. Within a selected neighborhood, the same construction is applied recursively. The multiplier bound below measures the cost of these successive rescalings.

2.3 The cross-mass estimate

For x\ge1, define

The function g_x is nondecreasing on [0,\infty). On (0,1) its derivative is x+\log(1/s)-1\ge0, and on (1,\infty) it is x; the formulas agree continuously at s=1 and s=0.

Lemma 2.3 is the only consequence of extremality needed in the weighted triangle argument. That argument can therefore be formulated for any positive weighted graph satisfying (2.5) with some constant C.

3 From cross mass to triangle mass

The triangle argument will replace vertices by copies carrying their full original weights. Total vertex weight can therefore increase. The rule that makes this operation useful is that each original edge is retained at most once. We show that this rule preserves the cross-mass bound and controls edge and triangle masses, so the subsequent argument can proceed without maximizing weights anew.

Retain the notation M_G(w), T_G(w), e_w(A,B) and g_x from the preceding sections. We write e_{G,w} when the graph must be specified. We say that (G,w) satisfies the cross-mass bound with constant C if, for every x\ge1 and every A,B\subseteq V(G),

We will repeatedly split vertices so as to reduce neighborhood weights, while retaining a fixed proportion of triangle weight. The cross-mass bound is the information that passes from one step to the next. We first verify this preservation and record the effect of deleting edges whose common-neighbor weight is small. The proof of Theorem 3.1 concludes after the splitting construction and its iteration.

3.1 Preservation and triangle counting

Edge deletion and vertex deletion are special cases of Lemma 3.2, using the inclusion map. The splitting operation used below is another special case: replace a vertex u by copies indexed by groups of its incident edges, give every copy weight w_u, and retain each original edge at most once, between its assigned endpoint copies. No assumption about optimization is required after these operations.

4 Local walks and entropy

We construct probability distributions on each neighborhood so that rows indexed by the other two vertices of a triangle are close on average, with the average weighted by triangle mass. We obtain the rows by running a weighted random walk. The cross-mass estimate bounds the average entropy by showing that most starting rows, in this weighted average, put almost all their probability on sets of small weight inside their neighborhoods. The resulting estimate is independent of the number of vertices. The use of entropy increments to control averaged distances between walk distributions has a precedent in Benjamini, Duminil-Copin, Kozma and Yadin [5, Section 2]. We prove the finite weighted version needed here, using the cross-mass hypothesis to bound its entropy.

Let G be a finite simple graph with positive weights satisfying (3.1) with constant C\ge1. Fix x\ge32 and suppose further that G has an edge and

Put

for every vertex u, with the empty sum equal to zero. We use kernels only at non-isolated vertices. At such a vertex u, set

These quantities are positive, and

On the finite set N(u) define stochastic matrices

Thus P_u is the weighted random walk on the induced graph G[N(u)], and Q_u adds probability 1/2 of staying at the current vertex. The row K_u^j(v,\cdot) is the law after one P_u-step from v followed by j such lazy steps. The initial step gives P_u(v,y)\le xw_y; we will show that subsequent steps preserve this density bound. The holding probability will let us compare rows started at adjacent vertices through an entropy increment. The superscript in K_u^j indexes this family, rather than denoting a power of a fixed kernel. We shall choose one index j for all neighborhoods.

Here are the probability laws used in the argument. Put

where both orientations of each edge occur in the sum defining Z. The conditional distribution of v given u under \mu is \pi_u. If, after sampling (u,v) from \mu, we sample z from P_u(v,\cdot), then

We call this the ordered triangle law.

For a probability vector a supported on vertices with positive weights, write

Thus H_j is an average of row entropies relative to the vertex weights; the weights themselves need not sum to one. For probability vectors a,b on the same finite set, write

The neighborhood bound s_u\le e^x alone allows row entropy as large as x. The next lemma improves the averaged upper bound to O_C(\log x) over \lceil x\rceil steps. Since the entropy increments are nonnegative, some step has small averaged increment; this will give the required comparison under the ordered triangle law.

5 Splitting vertices and bounding triangle mass

The local walks give similar probability distributions to the two neighbors at a corner of a triangle, on average under the ordered triangle law. We now sample from these distributions jointly. Equal samples keep the two incident edges of a triangle at the same copy of a vertex. A condition on the reversed transition probability ensures that each copy has a small weighted neighborhood.

5.1 Sampling all rows together

We use the shared rejection construction of Kleinberg and Tardos [11, Section 3, Lemmas 3.1 and 3.2]. Angel and Spinka [4, Theorem 2 and Section 2.1] give the sharper pairwise disagreement estimate stated below. The short proof supplies the joint law for all rows at once.

5.2 Admissible labels and vertex splitting

Let H be a finite graph with positive vertex weights. Assume that every edge uv has common-neighbor weight c_{uv}\ge1/x, that every neighborhood has weight at most e^x, and that H satisfies the cross-mass condition (3.1) with constant C\ge1. Here x\ge32. If H has an edge, then it has a triangle; throughout this subsection suppose T_H(w)>0.

Use the integer j supplied by Lemma 4.1, and for each non-isolated vertex u write K_u=K_u^j for the corresponding kernel on N_H(u). Isolated vertices may be discarded, since they contribute neither edge nor triangle mass. The directed-edge probability measure is

Conditional on u, its second coordinate has distribution \pi_u(v)=w_vc_{uv}/h_u, and K_u is reversible for \pi_u. We use the constants from that lemma:

In particular, K_u(v,y)\le xw_y, the averaged row entropy is at most A_C\log x, and the average total variation distance between the rows indexed by the other two vertices of a weighted ordered triangle is at most B_C\sqrt{\log x/x}.

For each non-isolated u, apply Lemma 5.1 to all rows of K_u. Denote the label assigned to v\in N_H(u) by Y_{u,v}. These finite joint laws may be sampled independently for different vertices u. We will group the neighbors of u according to their labels, while keeping the total weight of each group at most e^{\sqrt x}. For this purpose, call a label y at the incidence (u,v) admissible if

For a fixed outcome of the labels, define

The reversed transition in (5.1) is chosen so that all vertices in one group can be compared with a single probability row:

This holds for every outcome of the labels. The next lemma shows that the admissibility requirement rejects only a small fraction of incidences under the triangle distribution.

We now turn the groups into a graph, for each fixed outcome of the labels. Make one vertex (u,y) of weight w_u for each nonempty group. For each edge uv of H whose two incidence labels are admissible, put an edge between (u,Y_{u,v}) and (v,Y_{v,u}). Call the resulting graph H'. Figure 1 shows the construction at one vertex. We take the maximum neighborhood weight of the empty graph to be zero.

5.3 Reduction and iteration

The preceding construction turns the walk estimates into a reduction of weighted neighborhoods. Choose X=X(C)\ge32 so large that

Such a choice depends only on C.

Applying Theorem 3.1 to the cross-mass bound of Lemma 2.3 gives the variational estimate needed for the independent-set argument: for every maximizer w on a finite K_r-free graph,

The zero-vertex case has both masses zero.

6 From triangle mass to independent sets

We now use the triangle estimate to choose independent vertices at a controlled cost in F_G^*. For an n-vertex K_r-free graph of maximum degree at most \Delta\ge3, a constant test weight gives F_G^* at least a constant multiple of n(\log\Delta)^2/\Delta. The triangle estimate will provide a vertex whose closed-neighborhood deletion costs at most a constant times \log\Delta. Induction compares these two bounds and gives the required independent set. We keep \Delta fixed throughout the induction, then pass to average degree by deleting high-degree vertices. Let B_r\ge0 be the constant in (5.10), and set