Open-problem statements, with their sources attached.

Alternative statement of Erdős Problem 835 using the chromatic number of the Johnson graph. This is equivalent to asking whether there exists $k > 2$ such that the chromatic number of the Johnson graph $J(2k, k)$ is $k+1$.

This is still open even if $|I_2| = 1$.

Is the chromatic number of J(2 * k, k) always at least k + 2?

It is perhaps true with two intervals replaced by any $k$ intervals.

Is it true that, for all large $n$, $f(n + 1) \ge f(n)$?

Is it true for any $k > 2$ that only finitely many $k$ intervals satisfy this condition?

Estimate m(n,k), or better give an asymptotic formula.

Is it true that, for all sufficiently large $k$, there exists finite intervals $I_1, \dotsc, I_k \subset \mathbb{N}$ with $|I_i| \geq 2$ for $1 \leq i \leq k$ such that

There exists a constant $C>0$ such that, for all large $N$, if $A\subseteq \{1,\ldots,N\}$ has size at least $\frac{5}{8}N+C$ then there are distinct $a,b,c\in A$ such that $a+b,a+c,b+c\in A$.

A problem of Erdős and Sós (also earlier considered by Choi, Erdős, and Szemerédi [CES75], but Erdős had forgotten this).

Let $n\geq 1$ and define $L_n$ to be the least common multiple of $\{1,\ldots,n\}$ and $a_n$ by $\sum_{1\leq k\leq n}\frac{1}{k}=\frac{a_n}{L_n}$.

Is it true that $(a_n,L_n)=1$ occurs for infinitely many $n$?

Erdős and Sós conjectured that $f_k(N)\sim \frac{1}{2}\left(1+\sum_{1\leq r\leq k-2}\frac{1}{4^r}\right) N$, where $f_k(N)$ is the minimal size of a subset of $\{1, \dots, N\}$ guaranteeing $k$ elements have all pairwise sums in the set.

This leads to a heuristic prediction (see for example a preprint of Shiu [Sh16]) of $\asymp\frac{x}{\log x}$ for the number of $n\in [1,x]$ such that $(a_n,L_n)=1$.

Erdős Problem 872, part (i) (weak form): there exists a constant $\epsilon > 0$ such that the game length is at least $\epsilon \cdot n$ for all sufficiently large $n$.

In particular, there should be infinitely many $n$, but the set of such $n$ should have density zero. Unfortunately this heuristic is difficult to turn into a proof.

Erdős Problem 872, part (ii) (strong form): for every $\epsilon > 0$, the game length is at least $(1-\epsilon) \cdot n / 2$ for all sufficiently large $n$.

Status note: the forum thread (April-May 2026) records Shortener strategies giving $L(n) \leq (23/48 + o(1)) \cdot n$ (described in the thread as accepted as correct, with a Lean formalization in progress) and a claimed $L(n) \leq 0.19 \cdot n$, either of which would answer this question negatively under the Prolonger-first convention. Neither is published, so the statement is recorded here as the original Erdős question.

If $A \subset \mathbb{N} has$\sum_{n \in A}\frac 1 n = \infty$, then must$A$ contain arbitrarily long arithmetic progressions?

Forum-related variant: how small can a maximal primitive subset of $\{2, \dots, n\}$ be? The set of primes in $\{2, \dots, n\}$ is a maximal primitive subset of size $\pi(n)$, and the forum thread asks whether this is the smallest possible for all $n \geq 2$. Equivalently: must every completed play of the saturation game, by both players and regardless of strategy, claim at least $\pi(n)$ elements? (Terminal positions of the game are exactly the maximal primitive subsets.)

Is it true that, for every $\varepsilon > 0$, $h(N) = \sqrt N + O_{\varespilon}(N^\varespilon)

Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A \ B is not a basis of order k.

Must there exist an infinite B ⊂ A such that A \ B is an additive basis of order k + 1?

Is it true that $N(b) \ll \log \log b$?