Problem 191

Let $C>0$ be arbitrary. Is it true that, if $n$ is sufficiently large depending on $C$ , then in any $2$ -colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subseteq \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and

\sum_{x\in X}\frac{1}{\log x}\geq C?

Source: erdosproblems.com/191

Combinatorics
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved: the site labels the problem PROVED (LEAN). The answer is yes: Rödl (J. Combin. Theory Ser. A 102 (2003), 229--240) proved that $f(n)\to\infty$ , with $f(n)=\Omega(\log\log\log\log n/\log\log\log\log\log n)$ , the rate both second-hand accounts give (under Rödl's results below), and gave a coloring showing $f(n)=O(\log\log\log n)$ ; Theorem 1.1 of Conlon, Fox and Sudakov (Duke Math. J. 162 (2013), 2903--2927) gives $f(n)\ge2^{-8}\log\log\log n$ for large $n$ , so $f(n)=\Theta(\log\log\log n)$ . Rödl's paper is not held, so his results are quoted second-hand from the Conlon--Fox--Sudakov introduction, the site and Erdős's 1982 report; the refereed theorem of Conlon, Fox and Sudakov (cited from the arXiv version headed "Accepted for publication in Duke Mathematical Journal") answers the question on its own. The site's "(Lean)" suffix is a catalog label explained under Formalization: an external Lean file that declares itself a formalization of Rödl's result states the problem and claims a proof (not built or checked here); it is linked from Rödl's claim page. The claim pages Rödl 2003 and Conlon, Fox and Sudakov 2011 record the two refereed proofs with their postings and acceptance evidence; the frontmatter standing derives from these pages.

Ro03: Rödl, V., On homogeneous sets of positive integers. J. Combin. Theory Ser. A 102 (2003), no. 1, 229--240; DOI 10.1016/S0097-3165(03)00026-8 (the Crossref record carries the publisher's open-archive license from 17 July 2013). Not held. Quoted here from [CFS13] pp. 2--3 and from the site.
CFS13: Conlon, D., Fox, J. and Sudakov, B., Two extensions of Ramsey's theorem. Duke Math. J. 162 (2013), no. 15, 2903--2927; DOI 10.1215/00127094-2382566; arXiv:1112.1548v2 (16 October 2013). Theorem 1.1 on p. 3, the definitions and Rödl's results on pp. 2--3, Conjecture 5.1 on p. 15 (preprint pages). Library home: Conlon, Fox and Sudakov 2013; result page Conlon, Fox and Sudakov 2013, Theorem 1.1.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; the passage on p. 15 of the re-typeset copy, which has its own pagination (the site's locator). Library home: Erdős 1981 (the passage is quoted below).
ErGr79: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. L'Enseignement Math. (2) 25 (1979), 325--344; printed p. 333. Library home: Erdős and Graham 1979.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980); printed p. 17, the same passage as [ErGr79]. Library home: Erdős and Graham 1980.
Er82e: Erdős, P., Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; printed p. 78. Library home: Erdős 1982.

Problem 191

Status

Proof claims

Discussion