Let $k \geq 3$ be fixed. Ramsey's theorem says that if $n$ is sufficiently large and we color the edges of the complete graph $K_n$ red or blue, there must be at least one monochromatic $K_k$. As it turns out, it's not just "at least one" but many: An averaging argument shows that as $n \rightarrow \infty$ a positive fraction of all the $\binom{n}{k}$ copies of $K_k$ in our coloring must be monochromatic.

This leads to a natural follow-up question: How few copies can we get? If we consider all $2$-colorings of $K_n$, which one (asymptotically) minimizes the number of monochromatic copies of $K_k$?

This was first studied for the case $k=3$ (monochromatic triangles) by Goodman, who in 1959 gave an explicit answer asymptotic to $\frac{1}{4} \binom{n}{3}$. The fraction $\frac{1}{4}$ has a natural interpretation here -- if we color randomly, this is the expected fraction of monochromatic triangles. Three years later, Erdős observed that the random coloring gives an upper bound of $2^{-\binom{k}{2}+1}$ on the minimum fraction of monochromatic $K_k$, and said it "seems likely" this was asymptotically optimal.

By 1980 Burr and Rosta conjectured that something even stronger was true: For any fixed graph $H$ the asymptotic way to minimize monochromatic copies of $H$ was just to color randomly. It wasn't until 1989 that Sidorenko gave a counterexample to the Burr-Rosta conjecture (a triangle with a pendant edge) and Thomason disproved Erdős's original conjecture by giving a coloring with significantly fewer monochromatic $K_4$ then random.

It is still an open question to determine the optimal coloring to minimize monochromatic $K_4$, and also still an open question to determine for which graphs the Burr-Rosta conjecture is true (such graphs are termed "common" in the literature).

Let $k \geq 3$ be fixed. Ramsey's theorem says that if $n$ is sufficiently large and we color the edges of the complete graph $K_n$ red or blue, there must be at least one monochromatic $K_k$. As it turns out, it's not just "at least one" but many: An averaging argument shows that as $n \rightarrow \infty$ a positive fraction of all the $\binom{n}{k}$ copies of $K_k$ in our coloring must be monochromatic.

This leads to a natural follow-up question: How few copies can we get? If we consider all $2$-colorings of $K_n$, which one (asymptotically) minimizes the number of monochromatic copies of $K_k$?

This was first studied for the case $k=3$ (monochromatic triangles) by Goodman, who in 1959 gave an explicit answer asymptotic to $\frac{1}{4} \binom{n}{3}$. The fraction $\frac{1}{4}$ has a natural interpretation here -- if we color randomly, this is the expected fraction of monochromatic triangles. Three years later, Erdős observed that the random coloring gives an upper bound of $2^{-\binom{k}{2}+1}$ on the minimum fraction of monochromatic $K_k$, and said it "seems likely" this was asymptotically optimal.

By 1980 Burr and Rosta conjectured that something even stronger was true: For any fixed graph $H$ the asymptotic way to minimize monochromatic copies of $H$ was just to color randomly. It wasn't until 1989 that Sidorenko gave a counterexample to the Burr-Rosta conjecture (a triangle with a pendant edge) and Thomason disproved Erdős's original conjecture by giving a coloring with significantly fewer monochromatic $K_4$ then random.

It is still an open question to determine the optimal coloring to minimize monochromatic $K_4$, and also still an open question to determine for which graphs the Burr-Rosta conjecture is true (such graphs are termed "common" in the literature).

Let $k \geq 3$ be fixed. Ramsey's theorem says that if $n$ is sufficiently large and we color the edges of the complete graph $K_n$ red or blue, there must be at least one monochromatic $K_k$. As it turns out, it's not just "at least one" but many: An averaging argument shows that as $n \rightarrow \infty$ a positive fraction of all the $\binom{n}{k}$ copies of $K_k$ in our coloring must be monochromatic.

This leads to a natural follow-up question: How few copies can we get? If we consider all $2$-colorings of $K_n$, which one (asymptotically) minimizes the number of monochromatic copies of $K_k$?

This was first studied for the case $k=3$ (monochromatic triangles) by Goodman, who showed in 1959 who gave an explicit answer asymptotic to $\frac{1}{4} \binom{n}{3}$. The fraction $\frac{1}{4}$ has a natural interpretation here -- if we color randomly, this is the expected fraction of monochromatic triangles. Three years later, Erdős observed that the random coloring gives an upper bound of $2^{-\binom{k}{2}+1}$ on the minimum fraction of monochromatic $K_k$, and said it "seems likely" this was asymptotically optimal.

By 1980 Burr and Rosta conjectured that something even stronger was true: For any fixed graph $H$ the asymptotic way to minimize monochromatic copies of $H$ was just to color randomly. It wasn't until 1989 that Sidorenko gave a counterexample to the Burr-Rosta conjecture (a triangle with a pendant edge) and Thomason disproved Erdős's original conjecture by giving a coloring with significantly fewer monochromatic $K_4$ then random.

It is still an open question to determine the optimal coloring to minimize monochromatic $K_4$, and also still an open question to determine for which graphs the Burr-Rosta conjecture is true (such graphs are termed "common" in the literature).

Let $k \geq 3$ be fixed. Ramsey's theorem says that if $n$ is sufficiently large and we color the edges of the complete graph $K_n$ red or blue, there must be at least one monochromatic $K_k$. As it turns out, it's not just "at least one" but many: An averaging argument shows that as $n \rightarrow \infty$ a positive fraction of all the $\binom{n}{k}$ copies of $K_k$ in our coloring must be monochromatic.

This leads to a natural follow-up question: How few copies can we get? If we consider all $2$-colorings of $K_n$, which one (asymptotically) minimizes the number of monochromatic copies of $K_k$?

This was first studied for the case $k=3$ (monochromatic triangles) by Goodman, who in 1959 gave an explicit answer asymptotic to $\frac{1}{4} \binom{n}{3}$. The fraction $\frac{1}{4}$ has a natural interpretation here -- if we color randomly, this is the expected fraction of monochromatic triangles. Three years later, Erdős observed that the random coloring gives an upper bound of $2^{-\binom{k}{2}+1}$ on the minimum fraction of monochromatic $K_k$, and said it "seems likely" this was asymptotically optimal.

By 1980 Burr and Rosta conjectured that something even stronger was true: For any fixed graph $H$ the asymptotic way to minimize monochromatic copies of $H$ was just to color randomly. It wasn't until 1989 that Sidorenko gave a counterexample to the Burr-Rosta conjecture (a triangle with a pendant edge) and Thomason disproved Erdős's original conjecture by giving a coloring with significantly fewer monochromatic $K_4$ then random.

It is still an open question to determine the optimal coloring to minimize monochromatic $K_4$, and also still an open question to determine for which graphs the Burr-Rosta conjecture is true (such graphs are termed "common" in the literature).