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 complete subgraphs of size $r$, where \[ 0.3\log n < r < 0.7\log n. \] The previously known lower bound on the total number of monochromatic complete subgraphs, due to Sz\'{ e}kely was $n^{ 0.1576\log n}$. We also prove that $G$ contains at least $n^{ \frac{ 1}{ 7} \log n} $ monochromatic complete subgraphs of size $\frac{ 1}{ 2}\log n$. If furthermore one assumes that the largest monochromatic complete subgraph in $G$ is of size $(\frac{ 1}{ 2} + o(1))\log n$ (it is a well known open question whether such graphs exist), then for every constant $0 \le c \le \frac{ 1}{ 2}$ we determine (up to low order terms) the number of monochromatic complete subgraphs of size $c \log n$. We do so by proving a lower bound that matches (up to low order terms) a previous upper bound of Sz\'{ e}kely. For example, the number of monochromatic complete subgraphs of size $\frac{ 1}{ 2} \log n$ is $n^{ \frac{ 1}{ 8}(4 - \log e \pm o(1))\log n} \simeq n^{ 0.32 \log n}$.

Categories: math.CO

On the Profile of Multiplicities of Complete Subgraphs