Open-problem statements, with their sources attached.

Any graph on $n$ vertices can be decomposed into $O(n)$ many edge-disjoint cycles and edges.

In [Er71] Erdős suggests that only $n-1$ many cycles and edges are required if we do not require them to be edge-disjoint.

What is the smallest $k$ such that $\mathbb{R}^2$ can be red/blue coloured with no pair of red points unit distance apart, and no $k$-term arithmetic progression of blue points with distance 1?

Seems to be open, as of January 2025.

Let $S \subseteq \mathbb{Z}^3$ be a finite set and let $A = \lbrace a_1, a_2, \ldots \rbrace$ be an infinite $S$-walk, so that $a_{i+1} - a_i \in S$ for all $i$. Must $A$ contain three collinear points?

What is the largest $k$ such that in any permutation of $\mathbb{Z}$ there must exist a monotone $k$-term arithmetic progression $x_1 < \cdots < x_k$?

Must every permutation of $\mathbb{N}$, contain a monotone 4-term arithmetic progression?

Can $\mathbb{N}$ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?

Is it true that $f(n,k) < c_k^n$ for some constant $c_k>0$ and for all $n > 0$?

Does the longest arithmetic progression of primes in $\{1,\ldots,N\}$ have length $o(\log N)$?

Is there an integer $m$ with $(m, 6) = 1$ such that none of $2^k \cdot 3^\ell \cdot m + 1$ are prime, for any $k, \ell \ge 0$?

Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?

Let $f(n)$ count the number of solutions to $n=p+2^k$ for prime $p$ and $k\geq 0$. Show that $f(n)=o(\log n)$.

Is it true that $f(N)\sim N^{1/3}$?

Originally asked to Erdős by Bose.

This is discussed in problem C11 of Guy's collection [Gu04].

More generally, Bose and Chowla [BoCh62] conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then $\lvert A\rvert \sim N^{1/r}.$

Let $N\geq 1$. What is the largest $t$ such that there are $A_1,\ldots,A_t\subseteq \{1,\ldots,N\}$ with $A_i\cap A_j$ a non-empty arithmetic progression for all $i\neq j$?

Szabo asks whether the maximal $t$ is given by

Is there a covering system all of whose moduli are of the form $p-1$ for some primes $p \geq 5$?

Let $A\subseteq \mathbb{N}$ be an infinite set and consider the following greedy algorithm for a rational $x\in (0,1)$: choose the minimal $n\in A$ such that $n\geq 1/x$ and repeat with $x$ replaced by $x-\frac{1}{n}$. If this terminates after finitely many steps then this produces a representation of $x$ as the sum of distinct unit fractions with denominators from $A$.

Does this process always terminate if $x$ has odd denominator and $A$ is the set of odd numbers?

More generally, for which pairs $x$ and $A$ does this process terminate?