Irreducible coverings by cliques and Sperner's theorem (Q1856342)

Suppose there is an irreducible covering of the \(n\) vertices of a graph \(G\) by \(n-k\) cliques. The author shows that this implies that the size of the largest clique of \(G\) is at most \(k+1\), if \(k= 2\) or \(3\), and at most \({k\choose [k/2]}\) if \(k\geq 4\). The bounds are best possible if \(n\) is sufficiently large with respect to \(k\).