2 ms·
So cool. On the one hand, going from n/3 to (n/3 + log log n) seems like such a small improvement, but as the article shows, the history is formidable: - n/3 (
by svat 1y ago
So cool. On the one hand, going from n/3 to (n/3 + log log n) seems like such a small improvement, but as the article shows, the history is formidable:
- n/3 (Erdős, 1965)
- (n+1)/3 (Alon and Kleitman, 1990)
- (n+2)/3 (Bourgain, 1997)
- n/3 + Ω(log log n) (this paper, Benjamin Bedert, https://arxiv.org/abs/2502.08624 https://arxiv.org/abs/2502.08624)
And the upper bound:
- n/3 + o(n) (Eberhard, Green, Manners, 2014).
Ben Green's list of 100 open problems is which this is (was?) Problem 1, is here: https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf https://people.maths.ox.ac.uk/greenbj/papers/open-problems.p...