OPEN - $500

If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\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 $[0,Nn)$. Erdős and Moser [Er56] proved
\[ N\geq (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\]
(In [Er85c] Erdős offered \$100 for any improvement of the constant $1/4$ here.)

A number of improvements of the constant have been given (see [St23] for a history), with the current record $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason. Two proofs achieving this constant are provided by Dubroff, Fox, and Xu [DFX21], who in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.

In [Er73] and [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. (The second proof of [DFX21] applies also to this generalisation.)

This problem appears in Erdős' book with Spencer [ErSp74] in the final chapter titled 'The kitchen sink'. As Ruzsa writes in [Ru99] "it is a rich kitchen where such things go to the sink".

The sequence of minimal $N$ for a given $n$ is A276661 in the OEIS.

See also [350].

OPEN - $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)?\]

A problem of Erdős and Turán. 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]. Both proofs in fact give
\[h(N) \leq N^{1/2}+N^{1/4}+1.\]
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$.

OPEN - $500

Is there an infinite Sidon set $A\subset \mathbb{N}$ such that
\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]
for all $\epsilon>0$?

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\]
and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

OPEN - $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?\]

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

OPEN

Let $N\geq 1$ and $A\subset \{1,\ldots,N\}$ be a Sidon set. Is it true that, for any $\epsilon>0$, there exist $M=M(\epsilon)$ and $B\subset \{N+1,\ldots,M\}$ such that $A\cup B\subset \{1,\ldots,M\}$ is a Sidon set of size at least $(1-\epsilon)M^{1/2}$?

See also [707].

OPEN - $250

Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$
\[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\]

The sum-product problem. Erdős and Szemerédi [ErSz83] proved a lower bound of $\lvert A\rvert^{1+c}$ for some constant $c>0$, and an upper bound of
\[\lvert A\rvert^2 \exp\left(-c\frac{\log\lvert A\rvert}{\log\log \lvert A\rvert}\right)\]
for some constant $c>0$. The lower bound has been improved a number of times. The current record is
\[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{1558}{1167}-o(1)}\]
due to Rudnev and Stevens [RuSt22] (note $1558/1167=1.33504\cdots$).

There is likely nothing special about the integers in this question, and indeed Erdős and Szemerédi also ask a similar question about finite sets of real or complex numbers. The current best bound for sets of reals is the same bound of Rudnev and Stevens above. The best bound for complex numbers is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}},\] due to Solymosi [So05].

One can in general ask this question in any setting where addition and multiplication are defined (once one avoids any trivial obstructions such as zero divisors or finite subfields). For example, it makes sense for subsets of finite fields. The current record is that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{5/8}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{11}{9}+o(1)},\] due to Rudnev, Shakan, and Shkredov [RSS20].

There is also a natural generalisation to higher-fold sum and product sets. For example, in [ErSz83] (and in [Er91]) Erdős and Szemerédi also conjecture that for any $m\geq 2$ and finite set of integers $A$ \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation and [808] for a stronger form of the original conjecture. See also [818] for a special case.

SOLVED

Let $A$ be a finite set of integers. Is it true that, for every $k$, if $\lvert A\rvert$ is sufficiently large depending on $k$, then there are least $\lvert A\rvert^k$ many integers which are either the sum or product of distinct elements of $A$?

Asked by Erdős and Szemerédi [ErSz83]. Solved in this form by Chang [Ch03].

Erdős and Szemerédi proved that there exist arbitrarily large sets $A$ such that the integers which are the sum or product of distinct elements of $A$ is at most \[\exp\left(c (\log \lvert A\rvert)^2\log\log\lvert A\rvert\right)\] for some constant $c>0$.

See also [52].

OPEN - $100

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with
\[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\]
many edges contains a $C_4$?

The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice. Erdős [Er91] observes that there exist subgraphs with
\[\geq \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\]
many edges without a $C_4$ (for some constant $c>0$). He suggests that it 'perhaps not hopeless' to determine the threshold exactly.

A similar question can be asked for other even cycles.

See also [666] and the entry in the graphs problem collection.

SOLVED - $250

If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$-degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.

Conjectured by Erdős and Simonovits. Erdős offered \$250 for a proof and \$100 for a counterexample. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that
\[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [146] and [147] and the entry in the graphs problem collection.

OPEN - $500

If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then
\[\mathrm{ex}(n;H) \ll n^{2-1/r}.\]

Conjectured by Erdős and Simonovits. Open even for $r=3$. Alon, Krivelevich, and Sudakov [AKS03] have proved
\[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\]
They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

Spencer [Sp77] proved
\[R(4,k) \gg (k\log k)^{5/2}.\]
Ajtai, Komlós, and Szemerédi [AKS80] proved
\[R(4,k) \ll \frac{k^3}{(\log k)^2}.\]
This is true, and was proved by Mattheus and Verstraete [MaVe23], who showed that
\[R(4,k) \gg \frac{k^3}{(\log k)^4}.\]

This problem is #5 in Ramsey Theory in the graphs problem collection.

OPEN

Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_5$ and at least $\delta n^2$ edges then $G$ contains a set of $\gg_\delta n$ vertices containing no triangle.

A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, who could prove this is true for $\delta>1/16$, and could further prove it for $\delta>0$ if we replace $K_5$ with $K_4$.

They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620]) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle.

See also [579] and the entry in the graphs problem collection.

OPEN

Show that for any rational $\alpha \in [1,2]$ there exists a bipartite graph $G$ such that
\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]
Conversely, if $G$ is bipartite then must there exist some rational $\alpha$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}?\]

A problem of Erdős and Simonovits. Bukh and Conlon [BuCo18] proved the first problem holds if we weaken asking for the extremal number of a single graph to asking for the extreaml number of a finite family of graphs.

A rational $\alpha\in [1,2]$ for which the first problem holds is known as a Turán exponent. Known Turán exponents are:

- $\frac{3}{2}-\frac{1}{2s}$ for $s\geq 2$ (Conlon, Janzer, and Lee [CJL21]).
- $\frac{4}{3}-\frac{1}{3s}$ and $\frac{5}{4}-\frac{1}{4s}$ for $s\geq 2$ (Jiang and Qiu [JiQi20]).
- $2-\frac{a}{b}$ for $\lfloor b/a\rfloor^3 \leq a\leq \frac{b}{\lfloor b/a\rfloor+1}+1$ (Jiang, Jiang, and Ma [JJM20]).
- $2-\frac{a}{b}$ with $b>a\geq 1$ and $b\equiv \pm 1\pmod{a}$ (Kang, Kim, and Liu [KKL21]).
- $1+a/b$ with $b>a^2$ (Jiang and Qiu [JiQi23]),
- $2-\frac{2}{2b+1}$ for $b\geq 2$ or $7/5$ (Jiang, Ma, and Yepremyan [JMY22]).
- $2-a/b$ with $b\geq (a-1)^2$ (Conlon and Janzer [CoJa22]).

See also [713] and the entry in the graphs problem collection.

OPEN

Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ and at least $\delta n^2$ edges then $G$ contains an independent set of size $\gg_\delta n$.

A problem of Erdős, Hajnal, Sós, and Szemerédi, who could prove this is true for $\delta>1/8$.

See also [533] and the entry in the graphs problem collection.

OPEN

Let $n\geq 3$ and $G$ be a graph with $\binom{2n+1}{2}-\binom{n}{2}-1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$?

Faudree proved that this is true if $G$ has $2n+1$ vertices.

SOLVED

Does there exist some constant $c>0$ such that if $G$ is a graph with $n$ vertices and $\geq (1/8-c)n^2$ edges then $G$ must contain either a $K_4$ or an independent set on at least $n/\log n$ vertices?

A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS93]. In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that
\[\mathrm{rt}(n; 4,n/\log n)< (1/8-c)n^2?\]
Erdős, Hajnal, Sós, and Szemerédi [EHSS83] proved that for any fixed $\epsilon>0$
\[\mathrm{rt}(n; 4,\epsilon n)< (1/8+o(1))n^2.\]
Sudakov [Su03] proved that
\[\mathrm{rt}(n; 4,ne^{-f(n)})=o(n^2)\]
whenever $f(n)/\sqrt{\log n}\to \infty$.

Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that \[\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2\] whenever $f(n) =o(\sqrt{\log n/\log\log n})$.

See also [22] and the entry in the graphs problem collection.

SOLVED

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that, for every $\epsilon>0$, if $n$ is sufficiently large, every subgraph of $Q_n$ with
\[\geq \epsilon n2^{n-1}\]
many edges contains a $C_6$?

In [Er91] Erdős further suggests that perhaps, for every $k\geq 3$, there are constants $c$ and $a_k<1$ such that every subgraph with at least $cn^{a_k}2^n$ many edges contains a $C_{2k}$, where $a_k\to 0$ as $k\to \infty$.

The answer to this problem is no: Chung [Ch92] and Brouwer, Dejter, and Thomassen [BDT93] constructed an edge-partition of $Q_n$ into four subgraphs, each containing no $C_6$.

See also [86].

SOLVED

Let $f(m,n)$ be maximal such that any graph on $n$ vertices in which every induced subgraph on $m$ vertices has an independent set of size at least $\log n$ must contain an independent set of size at least $f(n)$.

Estimate $f(n)$. In particular, is it true that $f((\log n)^2,n) \geq n^{1/2-o(1)}$? Is it true that $f((\log n)^3,n)\gg (\log n)^3$?

A question of Erdős and Hajnal. Alon and Sudakov [AlSu07] proved that in fact
\[\frac{(\log n)^2}{\log\log n}\ll f((\log n)^2,n) \ll (\log n)^2\]
and
\[f((\log n)^3,n)\asymp \frac{(\log n)^2}{\log\log n}.\]

See also [805].

OPEN

For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an independent set of size $\geq \log n$?

In particular, is there such a graph for $g(n)=(\log n)^3$?

A problem of Erdős and Hajnal, who thought that there is no such graph for $g(n)=(\log n)^3$. Alon and Sudakov [AlSu07] proved that there is no such graph with
\[g(n)=\frac{c}{\log\log n}(\log n)^3\]
for some constant $c>0$.

Alon, Bucić, and Sudakov [ABS21] construct such a graph with \[g(n)\leq 2^{2^{(\log\log n)^{1/2+o(1)}}}.\] See also [804].

SOLVED

Let $c,\epsilon>0$ and $n$ be sufficiently large. If $A\subset \mathbb{N}$ has $\lvert A\rvert=n$ and $G$ is any graph on $A$ with at least $n^{1+c}$ edges then
\[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \geq \lvert A\rvert^{1+c-\epsilon},\]
where
\[A+_GA = \{ a+b : (a,b)\in G\}\]
and similarly for $A\cdot_GA$.

A problem of Erdős and Szemerédi, which strengthens the conjecture [52].

This strong conjecture was disproved by Alon, Ruzsa, and Solymosi [ARS20], who constructed (for arbitrarily large $n$) a set of integers $A$ with $\lvert A\rvert=n$ and a graph $G$ with $\gg n^{5/3-o(1)}$ many edges such that \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \ll \lvert A\rvert^{4/3+o(1)}.\] Alon, Ruzsa, and Solymosi do prove, however, that if $A$ has size $n$ and $G$ has $m$ edges then \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \gg m^{3/2}n^{-7/4}.\]

OPEN

Let $k\geq 3$ and define $F_k(n)$ to be the minimal $r$ such that there is a graph $G$ on $n$ vertices with $\lfloor n^2/4\rfloor+1$ many edges such that the edges can be $r$-coloured so that every subgraph isomorphic to $C_{2k+1}$ has no colour repeating on the edges.

Is it true that \[F_k(n)\sim n^2/8?\]

A problem of Burr, Erdős, Graham, and Sós, who proved that
\[F_k(n)\gg n^2.\]

See also [810].

OPEN

Does there exist some $\epsilon>0$ such that, for all sufficiently large $n$, there exists a graph $G$ on $n$ vertices with at least $\epsilon n^2$ many edges such that the edges can be coloured with $n$ colours so that every $C_4$ receives $4$ distinct colours?

A problem of Burr, Erdős, Graham, and Sós.

See also [809].

OPEN

For which graphs $G$ does the following hold: for all large $n$ there exists some $d_G(n)$ such that if $n$ is sufficiently large and the edges of $K_n$ are coloured with $e(G)$ many colours such that the minimum degree of each colour class is $\geq d_G(n)$ then there is a subgraph isomorphic to $G$ where each edge receives a different colour?

If $d_G(n)$ exists then determine the best possible value of $d_G(n)$.

A problem of Erdős, Pyber, and Tuza, who observe that if $d_G(n)$ exists then $d_G(n) < \frac{n-1}{e(G)}$.

The Kürschák competition in Hungary in 1986 asked students to prove that $d_{K_3}(n)$ exists. Kostochka proved that $d_{K_3}(n)=n/4$ is the best possible. Tuza proved that \[d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\] for some constant $c>0$. Brightwell and Trotter proved that \[d_{C_6}(n) > (1-o(1))\frac{n}{6}.\]

OPEN

Is it true that
\[\frac{R(n+1)}{R(n)}\geq 1+c\]
for some constant $c>0$, for all large $n$? Is it true that
\[R(n+1)-R(n) \gg n^2?\]

OPEN

Let $h(n)$ be minimal such that every graph on $n$ vertices where every set of $7$ vertices contains a triangle (a copy of $K_3$) must contain a clique on at least $h(n)$ vertices. Estimate $h(n)$ - in particular, do there exist constants $c_1,c_2>0$ such that
\[n^{1/3+c_1}\ll h(n) \ll n^{1/2-c_2}?\]

A problem of Erdős and Hajnal, who could prove that
\[n^{1/3}\ll h(n) \ll n^{1/2}.\]

Bucić and Sudakov [BuSu23] have proved \[h(n) \gg n^{5/12-o(1)}.\]

SOLVED

Let $k\geq 2$ and $G$ be a graph with $n\geq k-1$ vertices and
\[(k-1)(n-k+2)+\binom{k-2}{2}+1\]
edges. Does there exist some $c_k>0$ such that $G$ must contain an induced subgraph on at most $(1-c_k)n$ vertices with minimum degree at least $k$?

The case $k=3$ was a problem of Erdős and Hajnal [Er91]. The question for general $k$ was a conjecture of Erdős, Faudree, Rousseau, and Schelp [EFRS90], who proved that such a subgraph exists with at most $n-c_k\sqrt{n}$ vertices. Mousset, Noever, and Skorić [MNS17] improved this to
\[n-c_k\frac{n}{\log n}.\]
The full conjecture was proved by Sauermann [Sa19], who proved this with $c_k \gg 1/k^3$.

OPEN

Let $k\geq 3$ and $n$ be sufficiently large. Is it true that if $G$ is a graph with $n$ vertices and $2n-2$ edges such that every proper induced subgraph has minimum degree $\leq 2$ then $G$ must contain a copy of $C_k$?

A problem of Erdős and Hajnal, who could prove it for $3\leq k\leq 6$.

OPEN

Let $k\geq 3$ and define $g_k(n)$ to be the minimal $N$ such that $\{1,\ldots,N\}$ contains some $A$ of size $\lvert A\rvert=n$ such that
\[\langle A\rangle = \left\{\sum_{a\in A}\epsilon_aa: \epsilon_a\in \{0,1\}\right\}\]
contains no non-trivial $k$-term arithmetic progression. Estimate $g_k(n)$. In particular, is it true that
\[g_3(n) \gg 3^n?\]

A problem of Erdős and Sárközy who proved
\[g_3(n) \gg \frac{3^n}{n^{O(1)}}.\]

SOLVED

Let $A$ be a finite set of integers such that $\lvert A+A\rvert \ll \lvert A\rvert$. Is it true that
\[\lvert AA\rvert \gg \frac{\lvert A\rvert^2}{(\log \lvert A\rvert)^C}\]
for some constant $C>0$?

OPEN

Let $f(N)$ be maximal such that there exists $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$. Estimate $f(N)$.

Erdős and Freud [ErFr91] proved
\[\left(\frac{3}{8}-o(1)\right)N \leq f(N) \leq \left(\frac{1}{2}+o(1)\right)N,\]
and note that it is closely connected to the size of the largest quasi-Sidon set (see [840]).