Problem Statement
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\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and\[\sum_{x\in X}\frac{1}{\log x}\geq C?\]
Categories:
Combinatorics Ramsey Theory
Progress
The answer is yes, which was proved by Rödl [Ro03].In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then\[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and\[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]
Source: erdosproblems.com/191 | Last verified: January 14, 2026