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.

$500

If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=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

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\}$.

$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 $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}.\]

$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})}.\]

$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$.

$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

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$.