OctoInformBeta

A logarithmic independence bound for clique-free graphs

For a finite simple graph GG on n>0n>0 vertices, write E(G)E(G) for its set of unordered edges. Its average degree is d=2|E(G)|/nd=2|E(G)|/n. The independence number α(G)\alpha(G) is the largest size of an independent set in GG. For an integer r≥2r\ge2, the graph is KrK_r-free if no rr vertices are pairwise adjacent. All logarithms are natural. The problem is to bound α(G)\alpha(G) in terms of nn, dd and a fixed excluded clique size rr.

Ajtai, Komlós and Szemerédi proved the bound α(G)=Ω(nlog⁡d/d)\alpha(G)=\Omega(n\log d/d) for triangle-free graphs as d→∞d\to\infty. Ajtai, Erdős, Komlós and Szemerédi conjectured the same order for every fixed excluded clique size. For each fixed r≥4r\ge4, Shearer obtained α(G)=Ωr(nlog⁡d/(dlog⁡log⁡d))\alpha(G)=\Omega_r(n\log d/(d\log\log d)) for KrK_r-free graphs as d→∞d\to\infty.

The Lean library CliqueFree proves, as its Theorem 1.1, the principal result of the preprint: for every integer r≥4r\ge4, there is a constant cr>0c_r>0, depending only on rr, such that every finite simple KrK_r-free graph on nn vertices with average degree d≥2d\ge2 satisfies α(G)≥crnlog⁡d/d\alpha(G)\ge c_r n\log d/d.

For nonnegative vertex weights w=(wv)w=(w_v), the weight of a vertex set AA is w(A)=∑v∈Awvw(A)=\sum_{v\in A}w_v. The edge mass is MG(w)=∑{u,v}∈E(G)wuwvM_G(w)=\sum_{\{u,v\}\in E(G)}w_uw_v. The triangle mass is TG(w)=∑{u,v,z} a trianglewuwvwzT_G(w)=\sum_{\{u,v,z\}\text{ a triangle}}w_uw_vw_z, with each unordered triangle counted once. The convention at zero is 0log⁡0=00\log0=0. The variational functional is FG(w)=∑vwv(1−log⁡wv)−MG(w)F_G(w)=\sum_v w_v(1-\log w_v)-M_G(w). An optimizer is a nonnegative weight vector attaining the global maximum of FGF_G. The directed cross mass is ew(A,B)=∑u∈A∑v∈B:{u,v}∈E(G)wuwve_w(A,B)=\sum_{u\in A}\sum_{v\in B:\{u,v\}\in E(G)}w_uw_v. For x≥1x\ge1, the growth function is gx(s)=s(x+max⁡{0,log⁡(1/s)})g_x(s)=s(x+\max\{0,\log(1/s)\}) for s>0s>0, with gx(0)=0g_x(0)=0. The cross-mass bound with constant C≥1C\ge1 is the condition ew(A,B)≤Cgx(w(A))e_w(A,B)\le Cg_x(w(A)) for every x≥1x\ge1 and all vertex sets A,BA,B with w(A),w(B)≤exw(A),w(B)\le e^x. The Lean library’s Theorem 3.1 states that, for every C≥1C\ge1, there is a constant B>0B>0 depending only on CC such that TG(w)≤BMG(w)T_G(w)\le BM_G(w) for every finite simple graph with positive vertex weights satisfying this cross-mass bound. Its optimizer triangle bound states that, for every integer r≥2r\ge2, there is a constant Br>0B_r>0 depending only on rr such that TG(w)≤BrMG(w)T_G(w)\le B_rM_G(w) for every optimizer on every finite simple KrK_r-free graph.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.

The Lean library: CliqueFree

CliqueFree is a Lean library: 22 items, in six groups. Each has a page written by OctoInform, listed below.

Section 1. Introduction 2 items
  1. Independence and average degree Average degree for finite simple graphs.
  2. Theorem 1.1 A logarithmic bound for clique-free graphs.
Section 2. An extremal weight and its cross-mass bound 5 items
  1. Weighted graph masses and the variational functional Vertex weights and their variational potential.
  2. Lemma 2.1 The graph potential has a global maximizer.
  3. Lemma 2.2 Clique exclusion permits sparse random rescaling.
  4. The growth function A logarithmic correction to linear growth.
  5. Lemma 2.3 Clique-free optimizers have bounded cross mass.
Section 3. From cross mass to triangle mass 4 items
  1. The cross-mass property A uniform condition on cross mass.
  2. Theorem 3.1 A cross-mass condition controls triangle mass.
  3. Lemma 3.2 Cross mass bounds survive edge projections.
  4. Lemma 3.3 Edge peeling with controlled triangle loss.
Section 4. Local walks and entropy 2 items
  1. Local kernels, the triangle law and weighted entropy Local walks combine triangle weights and entropy.
  2. Lemma 4.1 Local walk smoothing controls neighboring rows.
Section 5. Splitting vertices and bounding triangle mass 7 items
  1. Lemma 5.1 Coupling finite families with controlled disagreement.
  2. Admissible labels and the splitting graph Splitting vertices by admissible incidence labels.
  3. Lemma 5.2 A weighted tail bound for reverse transitions.
  4. Lemma 5.3 Vertex splitting with controlled triangle loss.
  5. Proposition 5.4 A triangle mass bound under neighborhood reduction.
  6. Iteration in the proof of Theorem 3.1 Weighted triangle bounds at finite squaring scales.
  7. Optimizer triangle bound Triangle mass at a graph potential maximum.
Section 6. From triangle mass to independent sets 2 items
  1. Proposition 6.1 Uniform optimizer triangle bounds give independence estimates.
  2. Passing to average degree in the proof of Theorem 1.1 Half the vertices have controlled degree.

No item matches.