On the Profile of Multiplicities of Complete Subgraphs

Uriel Feige, Anne Kenyon, Shimon Kogan

Let $G$ be a $2$-coloring of a complete graph on $n$ vertices, for sufficiently large $n$. We prove that $G$ contains at least $n^{(\frac{1}{4}-o(1))\log n}$ monochromatic comple…