# Density of Ramsey subsets of $\omega$

For any set $$X$$ let $$[X]^2=\{\{x,y\}:x\neq y \in X\}$$. The starting point of this question is the following statement that follows from a more general theorem by Ramsey:

If $$\pi:[\omega]^2\to\{0,1\}$$ is any map, then here is an infinite set $$S\subseteq \omega$$ such that the restriction $$\pi|_{[S]^2}$$ is constant.

We call an infinite set $$S$$ with the above property a Ramsey set for the map $$\pi:[\omega]^2\to\{0,1\}$$. For $$A\subseteq \omega$$ we define its upper density $$d(A)\in [0,1]$$ by $$d(A) = \lim\sup_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}.$$

Question. Given a map $$\pi:[\omega]^2\to\{0,1\}$$, is there necessarily a Ramsey set $$S\subseteq \omega$$ with $$d(S)>0$$?

• It is worth mentioning the following result of Erdos and Galvin: in a coloring $f:[\omega]^2\to\{0,1,2\}$ there is an infinite set containing at least $c\log n$ elements below $n$ and spanning only 2 colors. Erdos, Galvin: Some Ramsey type theorems, Disc. Math., 87(1991), 261-269. Dec 24 '20 at 8:20
• @PéterKomjáth The set can't possibly contain "at least $c\log n$ elements below $n$" for all $n$. What is the correct statement? Is it something like "at least $c\log n$ elements below $n$ for infinitely many $n$"? But the set of $n$ for which that holds can be arbitrarily sparse?
– bof
Dec 26 '20 at 0:36
• To see that "the set of $n$ for which that holds can be arbitrarily sparse" consider a partition of $\omega$ into intervals $I_1\lt I_2\lt\cdots$ of rapidly increasing length and let $f(\{x,y\})=i\in\{0,1,2\}$ if $x,y\in I_{3m+i}$.
– bof
Dec 26 '20 at 0:50

Decompose $$\omega$$ into the disjoint union of the sets $$I_k$$ where $$I_k=[k!,(k+1)!-1]$$. Let $$f(x,y)$$ be 1 if $$x,y$$ are in distinct intervals, otherwise 0. It is easy to see that each homogeneous set for 1 is finite, for 0 has zero density.
If we define $$\pi: [\mathbb N]^2 \rightarrow \{0,1\}$$ randomly (say each $$\pi(a,b)$$ is determined by a coin flip), then almost surely there is no set $$S$$ with $$d(S) > 0$$ that is Ramsey for $$\pi$$. In fact, it is almost surely true that every $$S$$ with $$d(S) > 0$$ contains an induced isomorphic copy of the randomly colored infinite graph.
Even more: for a random coloring $$\pi$$ of $$[\mathbb N]^2$$, there is almost surely no set $$S$$ with $$\sum_{n \in S \setminus \{0\}} \frac{1}{n} = \infty$$ that is Ramsey for $$\pi$$. In fact, it is almost surely true that every such $$S$$ contains an induced copy of every coloring of every finite graph. (But in this case, "finite" cannot be improved to "infinite" as above.)