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

See also [350].

SOLVED - $1000

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

Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown the answer is no: the smallest modulus must be at most $10^{18}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the bound on the smallest modulus to $616000$.

OPEN - $5000

If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$ then must $A$ contain arbitrarily long arithmetic progressions?

This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like
\[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\]
would be sufficient.

Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp(-(\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.

Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08].

SOLVED - $10000

For any $C>0$ are there infinitely many $n$ such that
\[p_{n+1}-p_n> C\frac{\log\log n\log\log\log\log n}{(\log\log \log n)^2}\log n?\]

The peculiar quantitative form of Erdős' question was motivated by an old result of Rankin [Ra38], who proved there exists some constant $C>0$ such that the claim holds. Solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16]. The best bound available, due to all five authors [FGKMT18], is that there are infinitely many $n$ such that
\[p_{n+1}-p_n\gg \frac{\log\log n\log\log\log\log n}{\log\log \log n}\log n.\]
The likely truth is a lower bound like $\gg(\log n)^2$. In [Er97c] Erdős revised the value of this problem to \$5000 and reserved the \$10000 for a lower bound of $>(\log n)^{1+c}$ for some $c>0$.

OPEN

Let $C\geq 0$. Is there an infinite sequence of $n_i$ such that
\[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\]

Let $S$ be the set of limit points of $(p_{n+1}-p_n)/\log n$. This problem asks whether $S=[0,\infty]$. Although this conjecture remains unproven, a lot is known about $S$. Some highlights:

- $\infty\in S$ by Westzynthius' result [We31] on large prime gaps,
- $0\in S$ by the work of Goldston, Pintz, and Yildirim [GPY09] on small prime gaps,
- Erdős [Er55] and Ricci [Ri56] independently showed that $S$ has positive Lebesgue measure,
- Hildebrand and Maier [HiMa88] showed that $S$ contains arbitrarily large (finite) numbers,
- Pintz [Pi16] showed that there exists some small constant $c>0$ such that $[0,c]\subset S$,
- Banks, Freiberg, and Maynard [BFM16] showed that at least $12.5\%$ of $[0,\infty)$ belongs to $S$,
- Merikoski [Me20] showed that at least $1/3$ of $[0,\infty)$ belongs to $S$, and that $S$ has bounded gaps.

SOLVED - $100

Let $d_n=p_{n+1}-p_n$. Are there infinitely many $n$ such that $d_n<d_{n+1}<d_{n+2}$?

Conjectured by Erdős and Turán [ErTu48]. Shockingly Erdős offered \$25000 for a disproof of this, but as he comments, it 'is certainly true'.

Indeed, the answer is yes, as proved by Banks, Freiberg, and Turnage-Butterbaugh [BFT15] with an application of the Maynard-Tao machinery concerning bounded gaps between primes [Ma15]. They in fact prove that, for any $m\geq 1$, there are infinitely many $n$ such that \[d_n<d_{n+1}<\cdots <d_{n+m}\] and infinitely many $n$ such that \[d_n> d_{n+1}>\cdots >d_{n+m}.\]

OPEN

Is there a covering system all of whose moduli are odd?

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).

OPEN

Is every odd $n$ the sum of a squarefree number and a power of 2?

Odlyzko has checked this up to $10^7$. Granville and Soundararajan [GrSo98] have proved that this is very related to the problem of finding primes $p$ for which $2^p\equiv 2\pmod{p^2}$ (for example this conjecture implies there are infinitely many such $p$).

This is equivalent to asking whether every $n$ not divisible by $4$ is the sum of a squarefree number and a power of two. Erdős thought that proving this with two powers of 2 is perhaps easy, and could prove that it is true (with a single power of two) for almost all $n$.

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

In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.

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

Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly (in particular establishing an upper bound of $o(n!)$, for which Erdős awarded him the consolation prize of \$100), 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.\]

SOLVED

Is it true that for every $C>0$ if $n$ is large enough and $\mathcal{F}$ is an intersecting family of sets of size $n$ with $\lvert \mathcal{F}\rvert \leq Cn$ then there exists a set $S$ with $\lvert S\rvert \leq n-1$ which intersects every $A\in\mathcal{F}$?

Conjectured by Erdős and Lovász [ErLo75], who proved that this holds if $\lvert \mathcal{F}\rvert\leq \frac{8}{3}n-4$. Disproved by Kahn [Ka94] who constructed an infinite sequence of $\mathcal{F}$, each a family of sets of size $n\to\infty$, such that any set $S$ of size $n-1$ is disjoint from at least one set in $\mathcal{F}$. The Erdős-Lovász constant of $8/3$ has not been improved.

SOLVED

Let $\epsilon>0$ and $n$ be sufficiently large depending on $\epsilon$. Is there a graph on $n$ vertices with $\geq n^2/8$ many edges which contains no $K_4$ such that the largest independent set has size at most $\epsilon n$?

In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that (for sufficiently large $n$)
\[\mathrm{rt}(n; 4,\epsilon n)\geq n^2/8?\]

Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]

See also [615].

OPEN

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

The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky [BCL21], who proved that deleting at most $1.064n^2$ edges suffices.

SOLVED

Does every triangle-free graph on $5n$ vertices contain at most $n^5$ copies of $C_5$?

Győri proved this with $1.03n^5$, which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami, Hladky, Král, Norine, and Razborov [HHKNR13].

OPEN - $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 the hypothesis $\lvert A\cap [1,N]\rvert \gg N^{1/2}$ for all large $N$ suffices.

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$ are such that $A+B=\mathbb{N}$ then $\limsup 1_A\ast 1_B(n)=\infty$.

See also [40].

SOLVED

If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots $ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$.

Conjectured by Hajnal and Erdős and solved by Liu and Montgomery [LiMo20]. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

SOLVED

If $G$ is a graph which contains odd cycles of $\leq k$ different lengths then $\chi(G)\leq 2k+2$, with equality if and only if $G$ contains $K_{2k+2}$.

Conjectured by Bollobás and Erdős. Bollobás and Shelah have confirmed this for $k=1$. Proved by Gyárfás [Gy92], who proved the stronger result that, if $G$ is 2-connected, then $G$ is either $K_{2k+2}$ or contains a vertex of degree at most $2k$.

A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.

SOLVED

Is it true that the number of graphs on $n$ vertices which do not contain $G$ is
\[\leq 2^{(1+o(1))\mathrm{ex}(n;G)}?\]

If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [ErFrRo86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least
\[2^{(1+c)\mathrm{ex}(n;C_6)}\]
such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of
\[2^{O(\mathrm{ex}(n;G))}\]
holds for all $G$.

OPEN

Does every graph on $n$ vertices with $>\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$?

Conjectured by Erdős and Simonovits, who could not even prove that at least $2$ copies of $C_4$ are guaranteed.

He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.

OPEN

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n^c$ vertices?

OPEN

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) which is a subgraph of both $G_1$ and $G_2$?

Erdős, Hajnal, and Shelah have shown that $G_1$ and $G_2$ must both contain all sufficiently large cycles.

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

SOLVED - $500

If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $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.

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

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

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.

A similar question can be asked for other even cycles.

OPEN - $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 possible. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances.

A stronger form (see [604]) may be true: is there a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even $\gg n$ many such points, or even that this is true averaged over all points.

See also [661].

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

The unit distance problem. 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 [SST84]. In [Er83c] and [Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.

Part of the difficulty of this problem is explained by a result of Valtr (see [Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter [SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.

See a survey by Szemerédi [Sz16] for further background and related results.

OPEN

Suppose $A\subset \mathbb{R}^2$ has $\lvert A\rvert=n$ and minimises the number of distinct distances between points in $A$. Prove that for large $n$ there are at least two (and probably many) such $A$ which are non-similar.

For $n=5$ the regular pentagon is the unique such set (Erdős mysteriously remarks this was proved by 'a colleague').

SOLVED

If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances.

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n+1}{2}\rfloor$ distinct distances is still open. Fishburn in fact conjectures that if $R(x)$ counts the number of distinct distances from $x$ then
\[\sum_{x\in A}R(x) \geq \binom{n}{2}.\]

Szemerédi conjectured (see [Er97e]) that this stronger variant remains true if we only assume that no three points are on a line, and proved this with the weaker bound of $n/3$.

See also [660].

OPEN

If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart.

Conjectured by Erdős and Moser. Füredi [Fu90] proved an upper bound of $O(n\log n)$. A short proof of this bound was given by Brass and Pach [BrPa01]. The best known upper bound is
\[\leq n\log_2n+4n,\]
due to Aggarwal [Ag15].

Edelsbrunner and Hajnal [EdHa91] have constructed $n$ such points with $2n-7$ pairs distance $1$ apart. (This disproved an early stronger conjecture of Erdős and Moser, that the true answer was $\frac{5}{3}n+O(1)$.)

OPEN - $100

Does every convex polygon have a vertex with no other $4$ vertices equidistant from it?

Erdős originally conjectured this with no $3$ vertices equidistant, but Danzer found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex), and Fishburn and Reeds [FiRe92] have found a convex polygon on 20 points such that every vertex has three vertices equidistant from it (and this distance is the same for all vertices).

If this fails for $4$, perhaps there is some constant for which it holds?

Erdős suggested this as an approach to solve [96]. Indeed, if this problem holds for $k+1$ vertices then, by induction, this implies an upper bound of $kn$ for [96].

The answer is no if we omit the requirement that the polygon is convex (I thank Boris Alexeev and Dustin Mixon for pointing this out), since for any $d$ there are graphs with minimum degree $d$ which can be embedded in the plane such that each edge has length one (for example one can take the $d$-dimensional hypercube graph on $2^d$ vertices). One can then connect the vertices in a cyclic order so that there are no self-intersections and no three consecutive vertices on a line, thus forming a (non-convex) polygon.

OPEN

Let $h(n)$ be such that any $n$ points in $\mathbb{R}^2$, with no three on a line and no four on a circle, determine at least $h(n)$ distinct distances. Does $h(n)/n\to \infty$?

Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$. Erdős, Füredi, and Pach have improved this to
\[h(n) < n\exp(c\sqrt{\log n})\]
for some constant $c>0$.

OPEN - $100

Given $n$ points in $\mathbb{R}^2$, no five of which are on a line, the number of lines containing four points is $o(n^2)$.

There are examples of sets of $n$ points with $\sim n^2/6$ many collinear triples and no four points on a line. Such constructions are given by Burr, Grünbaum, and Sloane [BGS74] and Füredi and Palásti [FuPa84].

Grünbaum [Gr76] constructed an example with $\gg n^{3/2}$ such lines. Erdős speculated this may be the correct order of magnitude. This is false: Solymosi and Stojaković [SoSt13] have constructed a set with no five on a line and at least \[n^{2-O(1/\sqrt{\log n})}\] many lines containing exactly four points.

See also [102]. A generalisation of this problem is asked in [588].

OPEN

Let $A$ be a set of $n$ points in $\mathbb{R}^2$ such that all pairwise distances are at least $1$ and if two distinct distances differ then they differ by at least $1$. Is the diameter of $A$ $\gg n$?

Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Kanold proved the diameter is $\geq n^{3/4}$. The bounds on the distinct distance problem [89] proved by Guth and Katz [GuKa15] imply a lower bound of $\gg n/\log n$.

OPEN

For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $\geq r$ and chromatic number $\geq k$?

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $r=4$ case. The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.

In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]

OPEN

Is there some $F(n)$ such that every graph with chromatic number $\aleph_1$ has, for all large $n$, a subgraph with chromatic number $n$ on at most $F(n)$ vertices?

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number $\aleph_0$.

OPEN

If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges.

What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$?

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.

On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$.

See also [74].

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

If $p(z)\in\mathbb{C}[z]$ is a monic polynomial of degree $n$ then is the length of the curve $\{ z\in \mathbb{C} : \lvert p(z)\rvert=1\}$ maximised when $p(z)=z^n-1$?

SOLVED

If $p(z)$ is a polynomial of degree $n$ such that $\{z : \lvert p(z)\rvert\leq 1\}$ is connected then is it true that
\[\max_{\substack{z\in\mathbb{C}\\ \lvert p(z)\rvert\leq 1}} \lvert p'(z)\rvert \leq (\tfrac{1}{2}+o(1))n^2?\]

The lower bound is easy: this is $\geq n$ and equality holds if and only if $p(z)=z^n$. The assumption that the set is connected is necessary, as witnessed for example by $p(z)=z^2+10z+1$.

The Chebyshev polynomials show that $n^2/2$ is best possible here. Erdős originally conjectured this without the $o(1)$ term but Szabados observed that was too strong. Pommerenke [Po59a] proved an upper bound of $\frac{e}{2}n^2$.

Eremenko and Lempert [ErLe94] have shown this is true, and in fact Chebyshev polynomials are the extreme examples.

SOLVED

Let $p(z)=\prod_{i=1}^n (z-z_i)$ for $\lvert z_i\rvert \leq 1$. Then the area of the set where \[A=\{ z: \lvert p(z)\rvert <1\}\]
is $>n^{-O(1)}$ (or perhaps even $>(\log n)^{-O(1)}$).

Conjectured by Erdős, Herzog, and Piranian [ErHePi58]. The lower bound $\mu(A) \gg n^{-4}$ follows from a result of Pommerenke [Po61]. The stronger lower bound $\gg (\log n)^{-O(1)}$ is still open.

Wagner [Wa88] proves, for $n\geq 3$, the existence of such polynomials with \[\mu(A) \ll_\epsilon (\log\log n)^{-1/2+\epsilon}\] for all $\epsilon>0$.

OPEN

Let $G$ be a group and let $\Gamma(G)$ be the commuting graph of $G$, with vertex set $G$ and $x\sim y$ if and only if $xy=yx$. Let $h(n)$ be minimal such that if the largest independent set of $\Gamma(G)$ has at most $n$ elements then $\Gamma(G)$ can be covered by $h(n)$ many complete subgraphs. Estimate $h(n)$ as well as possible.

Pyber [Py87] has proved there exist constants $c_2>c_1>1$ such that $c_1^n<h(n)<c_2^n$.

SOLVED

Let $\alpha$ be a cardinal or ordinal number or an order type such that every two-colouring of $K_\alpha$ contains either a red $K_\alpha$ or a blue $K_3$. For every $n\geq 3$ must every two-colouring of $K_\alpha$ contain either a red $K_\alpha$ or a blue $K_n$?

Conjectured by Erdős and Hajnal. The answer is no, as independently shown by Schipperus [Sc99] (published in [Sc10]) and Darby [Da99].

For example, Larson [La00] has shown that this is false when $\alpha=\omega^{\omega^2}$ and $n=5$. There is more background and proof sketches in Chapter 2.9 of [HST10], by Hajnal and Larson.

SOLVED - $100

Let $z_i$ be an infinite sequence of complex numbers such that $\lvert z_i\rvert=1$ for all $i\geq 1$, and for $n\geq 1$ let
\[p_n(z)=\prod_{i\leq n} (z-z_i).\]
Let $M_n=\max_{\lvert z\rvert=1}\lvert p_n(z)\rvert$. Is it true that $\limsup M_n=\infty$? Is it true that there exists $c>0$ such that for infinitely many $n$ we have $M_n > n^c$, or even that for all $n$
\[\sum_{k\leq n}M_k > n^{1+c}?\]

The weaker conjecture that $\limsup M_n=\infty$ was proved by Wagner, who show that there is some $c>0$ with $M_n>(\log n)^c$ infinitely often.

This was solved by Beck [Be91], who proved that there exists some $c>0$ such that \[\max_{n\leq N} M_n > N^c.\]

OPEN - $100

Let $A\subseteq\mathbb{R}$ be an infinite set. Must there be a set $E\subset \mathbb{R}$ of positive measure which does not contain any set of the shape $aA+b$ for some $a,b\in\mathbb{R}$ and $a\neq 0$?

The Erdős similarity problem.

This is true if $A$ is unbounded or dense in some interval. It therefore suffices to prove this when $A=\{a_1>a_2>\cdots\}$ is a countable strictly monotone sequence which converges to $0$.

Steinhaus [St20] has proved this is false whenever $A$ is a finite set.

This conjecture is known in many special cases (but, for example, it is is open when $A=\{1,1/2,1/4,\ldots\}$. For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem.

OPEN

Let $\epsilon>0$ and $n$ be sufficiently large. Show that, if $G$ is a graph on $n$ vertices which does not contain $K_{2,2,2}$ and $G$ has at least $\epsilon n^2$ many edges, then $G$ contains an independent set on $\gg_\epsilon n$ many vertices.

A problem of Erdős, Hajnal, Sós, and Szemerédi.

OPEN - $500

Given $n$ distinct points $A\subset\mathbb{R}^2$ must there be a point $x\in A$ such that
\[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\]
Or even $\gg n/\sqrt{\log n}$?

The pinned distance problem, a stronger form of [89]. The example of an integer grid show that $n/\sqrt{\log n}$ would be best possible.

It may be true that there are $\gg n$ many such points, or that this is true on average. In [Er97e] Erdős offers \$500 for a solution to this problem, but it is unclear whether he intended this for proving the eixstence of a single such point or for $\gg n$ many such points.

In [Er97e] Erdős wrote that he initially 'overconjectured' and thought that the answer to this problem is the same as for the number of distinct distances between all pairs (see [89]), but this was disproved by Harborth. It could be true that the answers are the same up to an additive factor of $n^{o(1)}$.

The best known bound is \[\gg n^{c-o(1)},\] due to Katz and Tardos [KaTa04], where \[c=\frac{48-14e}{55-16e}=0.864137\cdots.\]