On the number of graphs without large cliques

Abstract

In 1976 Erdos, Kleitman and Rothschild determined the number of graphs without a clique of size $\ell$. In this note we extend their result to the case of forbidden cliques of increasing size. More precisely we prove that for ${\ell }_n\le \frac{1}{2}(\log n{)}^{1/4}$ there are $$2^{(1-1/({\ell }_n-1))n^2/2+o(n^2/{\ell }_n)}$$ $K_{{\ell }_n}$-free graphs of order $n$. Our proof is based on the recent hypergraph container theorems of Saxton, Thomason and Balogh, Morris, Samotij, in combination with a theorem of Lovasz and Simonovits.

References in corpus (3)

• Hypergraph containers
• The typical structure of graphs with no large cliques
• The number of graphs with large forbidden subgraphs

Cited by in corpus (5)

• Further applications of the Container Method
• An efficient container lemma
• The typical structure of graphs with no large cliques
• Higher Rédei reciprocity and integral points on conics
• On the typical structure of graphs not containing a fixed vertex-critical subgraph