For a finite simple graph on vertices, write for its set of unordered edges. Its average degree is . The independence number is the largest size of an independent set in . For an integer , the graph is -free if no vertices are pairwise adjacent. All logarithms are natural. The problem is to bound in terms of , and a fixed excluded clique size .
Ajtai, Komlós and Szemerédi proved the bound for triangle-free graphs as . Ajtai, Erdős, Komlós and Szemerédi conjectured the same order for every fixed excluded clique size. For each fixed , Shearer obtained for -free graphs as .
The Lean library CliqueFree proves, as its Theorem 1.1, the principal result of the preprint: for every integer , there is a constant , depending only on , such that every finite simple -free graph on vertices with average degree satisfies .
For nonnegative vertex weights , the weight of a vertex set is . The edge mass is . The triangle mass is , with each unordered triangle counted once. The convention at zero is . The variational functional is . An optimizer is a nonnegative weight vector attaining the global maximum of . The directed cross mass is . For , the growth function is for , with . The cross-mass bound with constant is the condition for every and all vertex sets with . The Lean library’s Theorem 3.1 states that, for every , there is a constant depending only on such that for every finite simple graph with positive vertex weights satisfying this cross-mass bound. Its optimizer triangle bound states that, for every integer , there is a constant depending only on such that for every optimizer on every finite simple -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.
CliqueFree is a Lean library: 22 items, in six groups. Each has a page written by OctoInform, listed below.
No item matches.