2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs (Q685676): Difference between revisions

Let \(k_ t(G)\) give the number of cliques of order \(t\) in graph \(G\), \(k_ t(n)= \min\bigl\{ k_ t(G)+ k_ t(\overline G): | V(G)|= n\bigr\}\), \(c_ t(n)= k_ t(n)/{n\choose t}\), and \(c_ t= \lim_{n\to\infty} c_ t(n)\). A conjecture by \textit{P. Erdős} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459-464 (1962; Zbl 0116.012)] that \(c_ t=2^{1-{t\choose 2}}\) was shown false by \textit{A. Thomason} [J. Lond. Math. Soc., II. Ser. 39, 246-255 (1989; Zbl 0638.05037)], for all \(t\geq 4\). The present authors give a class of simply described Cayley graphs which also show the falsity of the Erdős conjecture, for \(t=4\).