Lagmental Vicfred

A Random Coloring Gives an Exponential Ramsey Lower Bound by Vicfred

tags: mathematics, extremal combinatorics, probabilistic method, Ramsey theory

Counting expected monochromatic cliques shows that sufficiently large two-colorings avoid a fixed clique. I will separate the object being defined from the consequence being claimed.

Statement

Extremal combinatorics asks how large a structure can be while avoiding a forbidden configuration. The probabilistic method proves existence by showing \(\mathbf P(X=0)>0\) or \(\mathbf E[X]<1\).

$$ X=\#\{\text{monochromatic }K_k\} $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ \mathbf E[X]=\binom nk2^{1-\binom k2} $$

Worked algebra

The computation below is not a second theorem. It is a checksum for the definitions and a place to inspect the difficult LaTeX at full size.

$$ \binom nk2^{1-\binom k2}<1\Longrightarrow R(k,k)>n $$

Conceptual compression

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad X=\#\{\text{monochromatic }K_k\},\\[5pt] \mathsf{C}\;&:\quad \mathbf E[X]=\binom nk2^{1-\binom k2}. \end{aligned} $$

Caveat

An expectation below one proves that some outcome has zero bad objects only when the bad-object count is a nonnegative integer.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \mathbf E[X]=\binom nk2^{1-\binom k2} \end{gathered}} $$

A symbolic summary is trustworthy only because the example and limitation remain visible beside it. The box compresses the conclusion without hiding its origin.

This article was posted on Sun 19 June 2016. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.