5
$\begingroup$

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$?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 24, 2020 at 8:20
  • $\begingroup$ @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? $\endgroup$
    – bof
    Dec 26, 2020 at 0:36
  • $\begingroup$ 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}$. $\endgroup$
    – bof
    Dec 26, 2020 at 0:50

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for this beautiful and easy to understand example! $\endgroup$ Dec 23, 2020 at 13:42
6
$\begingroup$

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.)

These results can be found in Section 2 of my paper "Which subsets of the infinite random graph look random?" (Mathematical Logic Quarterly 64 (2018), pp. 478-486), available here.

$\endgroup$
1
  • $\begingroup$ Thanks both of you for the beautiful answers - I wish I could accept both! $\endgroup$ Dec 23, 2020 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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