We consider the following problem posed by Erdős in 1962. Suppose that $G$ is an $n$-vertex graph where the number of $s$-cliques in $G$ is $t$. How small can the independence number of $G$ be? Our main result suggests that for fixed $s$, the smallest possible independence number undergoes a transition at $t=n^{s/2+o(1)}$. In the case of triangles ($s=3$) our method yields the following result which is sharp apart from constant factors and generalizes basic results in Ramsey theory: there exists $c>0$ such that every $n$-vertex graph with $t$ triangles has independence number at least $$c \cdot \min\left\{ \sqrt {n \log n}\, , \, \frac{n}{t^{1/3}} \left(\log \frac{n}{ t^{1/3}}\right)^{2/3} \right\}.$$
@article{10_37236_7598,
author = {Tom Bohman and Dhruv Mubayi},
title = {Independence number of graphs with a prescribed number of cliques},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {2},
doi = {10.37236/7598},
zbl = {1412.05107},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7598/}
}
TY - JOUR
AU - Tom Bohman
AU - Dhruv Mubayi
TI - Independence number of graphs with a prescribed number of cliques
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7598/
DO - 10.37236/7598
ID - 10_37236_7598
ER -
%0 Journal Article
%A Tom Bohman
%A Dhruv Mubayi
%T Independence number of graphs with a prescribed number of cliques
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7598/
%R 10.37236/7598
%F 10_37236_7598
Tom Bohman; Dhruv Mubayi. Independence number of graphs with a prescribed number of cliques. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/7598
