8
$\begingroup$

I look for examples of Ramsey-type statements, for which the density counterparts do not hold.

Example: usual Ramsey theorem. If all edges of a complete graph $K_n$ are colored in $c$ colors, there is a monochromatic, say, triangle if $n>n_0(c)$ is large enough. But if we choose more than $\frac1c \binom{n}2$ edges, it may appear that there is no triangle formed by the chosen edges.

Another (related) example (Schur theorem): if we color $\{1,\dots,n\}$ in $c$ colors, there is a monochromatic solution of $x+y=z$. It is not true that if we choose a half of numbers, than there exists a solution of above equation with $x,y,z$ chosen. Say, we could choose only odd numbers.

On there other side, there are very important examples, when denisty versions are true (Szemeredi theorem, density Hales-Jewett and many others).

My question is to

1) give less trivial examples;

2) give some theorems or conjectures on when density versions hold and when fail.

$\endgroup$
2
  • 3
    $\begingroup$ I think your question is very broad, as it does not admit a concise answer, but asks for a survey instead. As far as I know there is no existing survey directly addressing your question. $\endgroup$
    – Boris Bukh
    Jul 19, 2016 at 20:59
  • $\begingroup$ @BorisBukh even several examples are welcome. I may add 'big-list' tag and make it CW if it is reasonable. $\endgroup$ Jul 20, 2016 at 6:25

1 Answer 1

5
$\begingroup$

Here are a few examples from graph-Ramsey theory. In the first pair of examples, the Ramsey version and density version are essentially as far apart as one can get. In the last two pairs of examples, the two versions coincide. Now I wonder if there is an example from graph-Ramsey theory where the bound from the density version is strictly stronger than the Ramsey version? But in general, it seems to me that your question could be narrowed down by simply asking for results in which the density version implies the Ramsey version, since those seem to be more rare.

1R) In every 2-coloring of $K_n$, there is a monochromatic connected subgraph on $n$ vertices. (Folklore)
1D) Every graph on $n$ vertices with at least $\binom{n-1}{2}+1$ edges is connected. (Folklore)

2R) In every 2-coloring of $K_n$, there is a monochromatic path on at least $2n/3$ vertices. (Gerencsér, Gyárfás)
2D) Every graph one $n$ vertices with at least $\frac{2}{3}\binom{n}{2}$ edges has a path on at least $2n/3$ vertices. (Erdős, Gallai)

3R) In every 2-coloring of $K_n$, there is a monochromatic matching covering at least $2n/3$ vertices. (Cockayne, Lorimer)
3D) Every graph on $n$ vertices with at least $\frac{5}{9}\binom{n}{2}$ edges has a matching covering at least $2n/3$ vertices. (Erdős, Gallai)

4R) In every 2-coloring of $K_n$, there is a monochromatic copy of every tree $T$ with at most $n/2+1$ vertices. Furthermore, there are trees with more than $n/2+1$ vertices for which this is not true. (Burr-Erdős conjecture, solved for large $n$ by Zhao)
4D) Every graph on $n$ vertices with at least $\frac{1}{2}\binom{n}{2}$ edges contains every tree with at most $n/2+1$ vertices. (Erdős, Sós conjecture)

5R) In every $r$-coloring of $K_{n,n}$, there is a monochromatic connected subgraph on at least $2n/r$ vertices and this is essentially best possible. (Gyárfás)
5D) Every balanced bipartite graph on $2n$ vertices with at least $n^2/r$ edges has a connected subgraph on at least $2n/r$ vertices and this is also best possible. (Gyárfás; Mubayi; Liu, Morris, Prince)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.