Ramsey multiplicity and the Turán coloring

Ramsey Theory is an area of combinatorics focused on the existence of well-behaved substructures. The most classical result of this kind is Ramsey’s Theorem, which in its simplest form asserts that for every integer \(n\), every \(2\)-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of the \(n\)-vertex complete graph. Other results of this kind include for example Van der Waerden’s theorem and the Hales-Jewett theorem.

The authors consider the quantitative version of Ramsey’s Theorem. Goodman’s Theorem from 1959 asserts that the number of monochromatic \(K_3\) in any \(2\)-edge-coloring of \(K_n\) is at least \(\frac{1}{4}\binom{n}{3}+O(n^2)\). In other words, the random \(2\)-edge-coloring of \(K_n\) asymptotically minimizes the number of monochromatic copies of \(K_3\). Erdős conjectured in 1962 that the same is true for the number of monochromatic copies of any complete graph and Burr and Rosta later conjectured the same to be true for any graph. The conjectures were disproved by Thomason and Sidorenko, respectively. In particular, there is a \(2\)-edge-coloring of \(K_n\) with the number of monochromatic copies of \(K_4\) below \(\frac{1}{33}\binom{n}{4}\).

The Ramsey multiplicity constant \(c(H)\) of a graph \(H\) is the largest number such that every \(2\)-edge-coloring of \(K_n\) contains at least \(\left(c(H)-o(1)\right) n^{v(H)}\) monochromatic labeled copies of \(H\), where \(v(H)\) is the number of vertices of \(H\). Note that the random \(2\)-edge-coloring minimizes the number of monchromatic copies of \(H\) iff \(c(H)=2^{1-e(H)}\), where \(e(H)\) is the number of edges of \(H\). Prior to this work, there was no graph \(H\) for which \(c(H)<2^{1-e(H)}\) and the value of \(c(H)\) was determined. The authors show that if \(H\) is a \(k\)-chromatic graph that contains an edge whose removal decreases the chromatic number, then adding sufficiently many pendant edges results in a graph with the Ramsey multiplicity constant equal to \((k-1)^{1-t-v(H)}\), where \(t\) is the number of added edges.