On the Profile of Multiplicities of Complete Subgraphs

Abstract

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é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é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}$.

slight improvements

References in corpus (1)

• On the Lovász Theta function for Independent Sets in Sparse Graphs