Erdős Problems

FAQ Tags Prizes Definitions Links

2 solved out of 6 shown

$1000

Can the smallest modulus of a covering system be arbitrarily large?

#2: [Er55c][Er61][Er57][ErGr80][Er90][Er95][Er97][Er97c]

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15] has shown the answer is no: the smallest modulus must be at most $10^{18}$.

$1000

Let $f(n,k)$ be minimal such that every $\mathcal{F}$ family of $n$-uniform sets with $\lvert F\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that \[f(n,k) < c_k^n\] for some constant $c_k>0$?

#20: [Er90][Er95][Er97c]

combinatorics

Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly, but the bound stood at $n^{(1+o(1))n}$ for a long time until Alweiss, Lovett, Wu, and Zhang [ALWZ20] proved \[f(n,k) < (Ck\log n\log\log n)^n\] for some constant $C>1$. This was refined slightly, independently by Rao [Ra20], Frankston, Kahn, Narayanan and Park [FKNP19], and Bell, Chueluecha and Warnke [BCW21], leading to the current record of \[f(n,k) < (Ck\log n)^n\] for some constant $C>1$. The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KoRoTa99] have shown \[f(n,k)=(1+O_n(k^{-1/2^n}))k^n.\]

Additional thanks to: Zachary Chase

$1000

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$, \[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]

#30: [Er61][Er95][Er97c]

number theory, sidon sets, additive combinatorics

It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield \[h(N)\leq N^{1/2}+0.99703N^{1/4}\] for sufficiently large $N$.

Additional thanks to: Zachary Hunter

$1000

Does every graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$?

#64: [Er95][Er97b]

graph theory, cycles

Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove much stronger result: if the average degree of $G$ is sufficiently large, then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

Additional thanks to: Yuval Wigderson

$1000

Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.

#139: [Er57][Er61][Er83c][Er97c]

additive combinatorics, arithmetic progressions

Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Gowers [Go01] for $k\geq 5$.

$1000

Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.

#142: [Er97c]

additive combinatorics, arithmetic progressions

The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Gowers [Go01] for $k\geq 5$. Erdős remarked this is 'probably unattackable at present'. Given that Erdős elsewhere offered \$5000 just for (essentially) showing that $r_k(N)=o_k(N/\log N)$, the value of this prize seems odd.