Logo
All Problems Random Solved Random Open
6 solved out of 19 shown
$500
If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in A'}a$ are distinct for all $A'\subseteq A$ then \[N \gg 2^{n}.\]
Erdős called this 'perhaps my first serious problem'. The powers of $2$ show that $2^n$ would be best possible here. The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset sums must lie in $\{1,\ldots,Nn\}$. Erdős and Moser [Er56] proved \[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\] A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ due to Dubroff, Fox, and Xu [DFX21].

In [ErGr80] the generalisation where $A\subseteq (0,N]$ is a set of real numbers such that the subset sums all differ by at least $1$ is proposed, with the same conjectured bound.

Additional thanks to: Zachary Hunter
$500
If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$?
Conjectured by Faber, Lovász, and Erdős. Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$. Hindman has proved the conjecture for $n<10$. Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.
$500
If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\limsup 1_A\ast 1_A(n)=\infty$.
Conjectured by Erdős and Turán. They also suggest the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$. Another stronger conjecture would be that $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ implies $\limsup 1_A\ast 1_A(n)=\infty$. Erdős and Sárközy conjectured the stronger version that if $A=\{a_1<a_2<\cdots\}$ and $B=\{b_1<b_2<\cdots\}$ with $a_n/b_n\to 1$ such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.
$500
For what functions $g(N)\to \infty$ is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}g(N)\] implies $\limsup 1_A\ast 1_A(n)=\infty$?
It is possible that this is true even with $g(N)=O(1)$, from which the Erdős-Turán conjecture would follow.
$500
Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\in A$ (aside from the trivial coincidences). Is it true that \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\] Is it true that \[\limsup \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=\infty?\]
Erdős proved that if the pairwise sums $a+b$ are all distinct aside from the trivial coincidences then \[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]
$500
Is there $A\subseteq \mathbb{N}$ such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is $\neq 0$?
A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárkzözy proved that \[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.
$500
If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist some $d,m\geq 1$ such that \[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\]
The 'Erdős discrepancy problem'. This is true, and was proved by Tao [Ta16], who also proved the more general case when $f$ takes values on the unit sphere.
$500
Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?
Conjectured by Erdős, Hajnal, and Szemerédi [ErHaSz82]. Rödl [Ro82] has proved this for hypergraphs. It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$.
$500
Suppose that we have a family $\mathcal{F}$ of subsets of $[4n]$ such that $\lvert A\rvert=2n$ for all $A\in\mathcal{F}$ and for every $A,B\in \mathcal{F}$ we have $\lvert A\cap B\rvert \geq 2$. Then \[\lvert \mathcal{F}\rvert \leq \frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}^2\right).\]
Conjectured by Erdős, Ko, and Rado [ErKoRa61]. This inequality would be best possible, as shown by taking $\mathcal{F}$ to be the collection of all subsets of $[4n]$ of size $2n$ containing at least $n+1$ elements from $[2n]$.

Proved by Ahlswede and Khachatrian [AhKh97], who more generally showed the following. Let $2\leq t\leq k\leq m$ and let $r\geq 0$ be such that \[\frac{1}{r+1}\leq \frac{m-2k+2t-2}{(t-1)(k-t+1)}< \frac{1}{r}.\] The largest possible family of subsets of $[m]$ of size $k$, such that the pairwise intersections have size at least $t$, is the family of all subsets of $[m]$ of size $k$ which contain at least $t+r$ elements from $\{1,\ldots,t+2r\}$.

Additional thanks to: Tuan Tran
$500
Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?
A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best possibe. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances. It may be true that there is a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even that there are $\gg n$ many such points, or even that this is true averaged over all points.
$500
Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?
This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter [SpSzTr84]. In [Er83c] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.
$500
Let $\epsilon>0$. Given any set of $n$ distinct points in $\mathbb{R}^2$ prove that each point is equidistant from $O_\epsilon(n^\epsilon)$ many other points.
Erdős only offers \$100 for a counterexample.
$500
Let $x_1,\ldots,x_n\in\mathbb{R}^2$ determine the set of distances $\{u_1,\ldots,u_t\}$. Suppose $u_i$ appears as the distance between $f(u_i)$ many pairs of points. Then for all $\epsilon>0$ \[\sum_i f(u_i)^2 \ll_\epsilon n^{3+\epsilon}.\]
The case when the points determine a convex polygon was been solved by Fishburn [Al63]. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$. Solved by Guth and Katz [GuKa15] who proved the upper bound \[ \sum_i f(u_i)^2 \ll n^3\log n.\]
$500
Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$.
The Erdős-Klein-Szekeres 'Happy Ending' problem. The problem originated in 1931 when Klein observed that $f(4)=5$. Turán and Makai showed $f(5)=9$. Erdős and Szekeres proved the bounds \[2^{n-2}+1\leq f(n)\leq \binom{2n-4}{n-2}+1.\] ([ErSz60] and [ErSz35] respectively). There were several improvements of the upper bound, but all of the form $4^{(1+o(1))n}$, until Suk [Su17] proved \[f(n) \leq 2^{(1+o(1))n}.\] The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos [HMPT20], who prove \[f(n) \leq 2^{n+O(\sqrt{n\log n})}.\]
Additional thanks to: Casey Tompkins
$500
Let $r_3(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $3$-term arithmetic progression. Prove that $r_3(N)\ll N/(\log N)^C$ for every $C>0$.
Proved by Kelley and Meka [KeMe23]. In [ErGr80] they suggest this holds for every $k$-term arithmetic progression.
$500
Let $A\subset \mathbb{R}$ be a countably infinite set (with $1\not\in A$) such that for all $x\neq y\in A$ and integers $k\geq 1$ we have \[ \lvert kx -y\rvert \geq 1.\] Does this imply that \[\sum_{x\in A}\frac{1}{x\log x}<\infty\] or \[\sum_{x <n}\frac{1}{x}=o(\log n)?\]
Note that if $A$ is a set of integers then the condition implies that $A$ is a primitive set (that is, no element of $A$ is divisible by any other), for which the convergence of $\sum_{n\in A}\frac{1}{n\log n}$ was proved by Erdős [Er35], and that $\sum_{n<x}\frac{1}{n}=o(\log x)$ was proved by Behrend [Be35].
$500
If $H$ is bipartite and every induced subgraph of $H$ has minimum degree $<r$ then \[\mathrm{ex}(n;H) \ll n^{2-1/(r-1)}.\]
Conjectured by Erdős and Simonovits. Open even for $r=3$.
$500
If $H$ is bipartite and there exists an induced subgraph of $H$ with minimum degree $\geq r$ then \[\mathrm{ex}(n;H) > n^{2+\epsilon-1/(r-1)}.\]
Conjectured by Erdős and Simonovits. Disproved by Janzer [Ja21].
Additional thanks to: Zachary Hunter
$500
Let $\alpha>0$ and $n,t\geq 1$ be integers. Let $F^{(t)}(n,\alpha)$ be the largest $k$ such that the following holds.

Let $\lvert S\rvert=n$ and 2-colour all $t$-subsets of $S$. For every $X\subseteq S$ of size at least $k$ there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Rado, and Hajnal implies that \[ F^{(t)}(n,0)\asymp \log_{t-1} n\] and results of Erdős and Spencer imply that \[F^{(t)}(n,\alpha) \asymp_\alpha (\log n)^{\frac{1}{t-1}}\] for $\alpha$ close to $1/2$.