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

In [Er81] offered \$1000 for a proof or disproof even just in the special case when $k=3$, which he expected 'contains the whole difficulty'. He also wrote 'I really do not see why this question is so difficult'.

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 [KRT99] have shown \[f(n,k)=(1+O_n(k^{-1/2^n}))k^n.\]

Conjectured by Erdős and Lovász [ErLo75], who proved that \[\frac{8}{3}n-3\leq f(n) \ll n^{3/2}\log n\] for all $n$. The upper bound was improved by Kahn [Ka92b] to \[f(n) \ll n\log n.\] (The upper bound constructions in both cases are formed by taking a random set of lines from a projective plane of order $n-1$, assuming $n-1$ is a prime power.)

This problem was solved by Kahn [Ka94] who proved the upper bound $f(n) \ll n$. The Erdős-Lovász lower bound of $\frac{8}{3}n-O(1)$ has not been improved, and it has been speculated (see e.g. [Ka94]) that the correct answer is $3n+O(1)$.

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

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 open when $A=\{1,1/2,1/4,\ldots\}$, which is Problem 94 on Green's open problems list). For an overview of progress we recommend a nice survey by Svetic [Sv00] on this problem. A survey of more recent progress was written by Jung, Lai, and Mooroogen [JLM24].

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

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$, \[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\] Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.

For all $\alpha>0$ it is known that \[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\] See also [563].

See also the entry in the graphs problem collection.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that \[c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.\]

The 'density Hales-Jewett' problem. This was proved by Furstenberg and Katznelson [FuKa91]. A new elementary proof, which gives quantitative bounds, was proved by the Polymath project [Po09].

The answer is yes, which was proved by Rödl [Ro03].

In the same article Rödl also proved a lower bound for this problem, constructing, for all $n$, a $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ such that if $X\subseteq \{2,\ldots,n\}$ is such that $\binom{X}{2}$ is monochromatic then \[\sum_{x\in X}\frac{1}{\log x}\ll \log\log\log n.\]

This bound is best possible, as proved by Conlon, Fox, and Sudakov [CFS13], who proved that, if $n$ is sufficiently large, then in any $2$-colouring of $\binom{\{2,\ldots,n\}}{2}$ there exists some $X\subset \{2,\ldots,n\}$ such that $\binom{X}{2}$ is monochromatic and \[\sum_{x\in X}\frac{1}{\log x}\geq 2^{-8}\log\log\log n.\]

This is true for $d\leq 3$ and false for $d\geq 4$.

This problem is equivalent to one on 'abelian squares' (see [231]). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.

This problem is therefore equivalent to asking for which $d$ there exists an infinite string over $\{1,\ldots,d\}$ with no abelian squares. It is easy to check that in fact any finite string of length $7$ over $\{1,2,3\}$ contains an abelian square.

An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results, and a blog post by Renan for an entertaining and educational discussion.

Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].

Erdős initially conjectured that the answer is yes for all $k\geq 2$, but for $k=4$ this was disproved by de Bruijn and Erdős. At least, this is what Erdős writes, but gives no construction or reference, and a simple computer search produces no such counterexamples for $k=4$. Perhaps Erdős meant $2^k$, where indeed there is an example for $k=4$: \[1213121412132124.\]

Erdős then asked if there is in fact an infinite string formed from $\{1,2,3,4\}$ which contains no abelian squares? This is equivalent to [192], and such a string was constructed by Keränen [Ke92]. The existence of this infinite string gives a negative answer to the problem for all $k\geq 4$.

Containing no abelian squares is a stronger property than being squarefree (the existence of infinitely long squarefree strings over alphabets with $k\geq 3$ characters was established by Thue).

We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results.

The estimate $\lvert \mathcal{F}\rvert=o(2^n)$ implies that if $A\subset \mathbb{N}$ is a set of positive density then there are infinitely many distinct $a,b,c\in A$ such that $[a,b]=c$ (i.e. [487]).

Solved by Kleitman [Kl71], who proved \[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]

Sperner's theorem states that $\lvert \mathcal{F}\rvert \leq \binom{n}{\lfloor n/2\rfloor}$. This is also known as Dedekind's problem.

Resolved by Kleitman [Kl69], who proved that the number of such families is \[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]

A strong form of the Littlewood-Offord problem. Erdős [Er45] proved this is true if $z_i\in\mathbb{R}$, and for general $z_i\in\mathbb{C}$ proved a weaker upper bound of \[\ll \frac{2^n}{\sqrt{n}}.\] This was solved in the affirmative by Kleitman [Kl65], who also later generalised this to arbitrary Hilbert spaces [Kl70].

See also [395].

A weaker form of the conjecture of van der Waerden, which states that \[\mathrm{perm}(M)=\sum_{\sigma\in S_n}\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}n!\] with equality if and only if $a_{ij}=1/n$ for all $i,j$.

This conjecture is true, and was proved by Marcus and Minc [MaMi62].

Erdős also conjectured the even weaker fact that there exists some $\sigma\in S_n$ such that $a_{i\sigma(i)}\neq 0$ for all $i$ and \[\sum_{i}a_{i\sigma(i)}\geq 1.\] This weaker statement was proved by Marcus and Ree [MaRe59].

van der Waerden's conjecture itself was proved by Gyires [Gy80], Egorychev [Eg81], and Falikman [Fa81].

Erdős and Hajnal [ErHa60] proved the existence of arbitrarily large finite independent sets (under the assumptions in the first problem).

Erdős writes in [Er61] that Gladysz has proved the existence of an independent set of size $2$ in the second question, but I cannot find a reference.

Hechler [He72] has shown the answer to the first question is no, assuming the continuum hypothesis.

A problem of Komjáth. The existence of such a $2$-colouring is sometimes known as Property B.

A problem of Komjáth. If instead we have $\lvert A_i\cap A_j\rvert \neq 1$ then Komjáth showed that this is possible with at most $\aleph_0$ colours.

A problem of Erdős and Hajnal [ErHa68] who proved that \[\log_2 n \leq H(n) < \log_2n +(3+o(1))\log_2\log_2n.\] Erdős said that even the weaker statement that for $n=2^k$ we have $H(n)\geq k+1$ is open, but Alon has provided the following simple proof: by the pigeonhole principle there are $\frac{n-1}{2}$ subsets $A_i$ of size $2$ such that $f(A_i)$ is the same. Any set $Y$ of size $k$ containing at least $k/2$ of them can have at most \[2^k-\lfloor k/2\rfloor+1< 2^k=n\] distinct elements in the union of the images of $f(A)$ for $A\subseteq Y$.

For this weaker statement, Erdős and Gyárfás conjectured the stronger form that if $\lvert X\rvert=2^k$ then, for any $f:\{A : A\subseteq X\}\to X$, there must exist some $Y\subset X$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}< 2^k-k^C\] for every $C$ (with $k$ sufficiently large depending on $C$). This was proved by Alon (personal communication), who proved the stronger version that, for any $\epsilon>0$, if $k$ is large enough, there must exist some $Y$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}<(1-\epsilon)2^k.\] Alon also proved that, provided $k$ is large enough, if $\lvert X\rvert=2^k$ there exists some $f:\{A: A\subseteq X\}\to X$ such that, if $Y\subset X$ with $\lvert Y\rvert=k$, then \[\#\{ f(A) : A\subseteq Y\}>\tfrac{1}{4}2^k.\]

A problem of Erdős, Fon-Der-Flaass, Kostochka, and Tuza [EFKT92], who proved that $f(k,3)=2k$ and $f(k,4)=\lfloor 3k/2\rfloor$ and $f(k,5)=\lfloor 5k/4\rfloor$, and further that $f(k,6)=k$.

This would imply in particular that in a finite geometry there is always a blocking set which meets every line in $O(1)$ many points.

In [Er81] the condition $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$ is replaced by every two points in $\{1,\ldots,n\}$ being contained in exactly one $A_i$, that is, $A_1,\ldots,A_m$ is a pairwise balanced block design (and the condition $c<1$ is omitted).

Alon has proved that the answer is no: if $q$ is a large prime power and $n=m=q^2+q+1$ then there exist $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that $\lvert A_i\rvert \geq \tfrac{2}{5}\sqrt{n}$ for all $i$ and $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$, and yet if $B$ has non-empty intersection with all $A_i$ then there exists $A_j$ such that $\lvert B\cap A_j\rvert \gg \log n$. (The construction is to take random subsets of the lines of a projective plane.)

The weaker version that Erdős posed in [Er81] remains open, although Alon conjectures the answer there to also be no.

A problem of Erdős and Larson [ErLa82].

Shrikhande and Singhi [ShSi85] have proved that the answer is no conditional on the conjecture that the order of every projective plane is a prime power (see [723]), by proving that every pairwise balanced design on $n$ points in which each block is of size $\geq n^{1/2}-c$ can be embedded in a projective plane of order $n+i$ for some $i\leq c+2$, if $n$ is sufficiently large.

Erdős asks if this is false for constant, for which functions $h(n)$ will the condition $\lvert A_i\rvert \geq n^{1/2}-h(n)$ make the conjecture true?

A problem of Chvátal [Ch74], who proved it when we replace the closed under subsets condition with the (stronger) condition that, assuming all sets in $\mathcal{F}$ are subsets of $\{1,\ldots,n\}$, whenever $A\in \mathcal{F}$ and there is an injection $f:B\to A$ such that $x\leq f(x)$ for all $x\in B$ then $B\in \mathcal{F}$.

Sterboul [St74] proved this when, letting $\mathcal{G}$ be the maximal sets (under inclusion) in $\mathcal{F}$, all sets in $\mathcal{G}$ have the same size, $\lvert A\cap B\rvert\leq 1$ for all $A\neq B\in \mathcal{G}$, and at least two sets in $\mathcal{G}$ have non-empty intersection.

Frankl and Kupavskii [FrKu23] have proved this when $\mathcal{F}$ has covering number $2$.

Borg [Bo11] has proposed a weighted generalisation of this conjecture, which he proves under certain additional assumptions.

A conjecture of Erdős and Sós. Katona (unpublished) proved this when $k=4$, and Frankl [Fr77] proved this for all $k\geq 4$.

See also [703].

It is trivial that $T(n,0)=2^{n-1}$. Frankl and Füredi [FrFu84b] proved that, for fixed $r$ and $n$ sufficiently large in terms of $r$, the maximal $T(n,r)$ is achieved by taking \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\rvert> \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is odd, and \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\backslash \{1\}\rvert\geq \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is even. (Frankl [Fr77b] had earlier proved this for $r=1$ and all $n$.)

An affirmative answer to the second question implies that the chromatic number of the unit distance graph in $\mathbb{R}^n$ (with two points joined by an edge if the distance between them is $1$) grows exponentially in $n$, which was proved by alternative methods by Frankl and Wilson [FrWi81] - see [704].

The answer to the second question is yes, proved by Frankl and Rödl [FrRo87].

See also [702].

This was proved for $(r,k)$ by:

• Kirkman for $(2,3)$;
• Hanani [Ha61] for $(3,4)$, $(2,4)$, and $(2,5)$;
• Wilson [Wi72] for $(2,k)$ for any $k$;
• Keevash [Ke14] for all $(r,k)$.

These always exist if $n$ is a prime power. This conjecture has been proved for $n\leq 11$, but it is open whether there exists a projective plane of order $12$.

Bruck and Ryser [BrRy49] have proved that if $n\equiv 1\pmod{4}$ or $n\equiv 2\pmod{4}$ then $n$ must be the sum of two squares. For example, this rules out $n=6$ or $n=14$. The case $n=10$ was ruled out by computer search [La97].

Euler conjectured that $f(n)=1$ when $n\equiv 2\pmod{4}$, but this was disproved by Bose, Parker, and Shrikhande [BPS60] who proved $f(n)\geq 2$ for $n\geq 7$.

Chowla, Erdős, and Straus [CES60] proved $f(n) \gg n^{1/91}$. Wilson [Wi74] proved $f(n) \gg n^{1/17}$. Beth [Be83c] proved $f(n) \gg n^{1/14.8}$.

The sequence of $f(n)$ is A001438 in the OEIS.

Erdős and Kaplansky [ErKa46] proved the count is \[\sim e^{-\binom{k}{2}}(n!)^k\] when $k=o((\log n)^{3/2-\epsilon})$. Yamamoto [Ya51] extended this to $k\leq n^{1/3-o(1)}$.

The count of such Latin rectangles is A001009 in the OEIS.

Erdős noted that a trivial necessary condition is $\sum_i \binom{X_i}{2}=\binom{n}{2}$, but wasn't sure if there would be a reasonable necessary and sufficient condition.

He could prove that there are \[\leq \exp(O(n^{1/2}\log n))\] many block-compatible sequences for $\{1,\ldots,n\}$.

Alon has proved there are at least \[2^{(\frac{1}{2}+o(1))n^{1/2}\log n}\]

many sequences which are block-compatible for $n$. See also [733].

This problem is essentially the same as [607], but with multiplicities.

Erdős writes that it is 'easy' to prove there are at least \[\exp(cn^{1/2})\] many such sequences for some constant $c>0$, but expected proving the upper bound to be difficult. Once it is done, he asked for the existence and value of \[\lim_{n\to \infty}\frac{\log f(n)}{n^{1/2}},\] where $f(n)$ counts the number of line-compatible sequences.

This is true, and was proved by Szemerédi and Trotter [SzTr83].

See also [732].

$A_1,\ldots,A_m$ is a pairwise balanced block design if every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$.

Erdős [Er81] writes 'this will be probably not be very difficult to prove but so far I was not successful'.

Erdős and de Bruijn [dBEr48] proved that if $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ is a pairwise balanced block design then $m\geq n$, and this implies there must be some $t$ such that there are $\gg n^{1/2}$ many $t$ with $\lvert A_i\rvert=t$.

Asked to Erdős by Shamir in 1979. This is often known as Shamir's problem. Erdős writes: 'Many of the problems on random hypergraphs can be settled by the same methods as used for ordinary graphs and usually one can guess the answer almost immediately. Here we have no idea of the answer.'

This is now essentially completely understood: Johansson, Kahn, and Vu [JKV08] proved that the threshold is $\ell(n)\asymp n\log n$. The precise asymptotic was given by Kahn [Ka23], proving that the threshold is $\sim n\log n$ (also for the general problem over $r$-uniform hypergraphs).

A problem of Erdős and Trotter. For $r=1$ and $n>3$ the maximum possible is $n-2$. For $r>1$ and $n$ sufficiently large $n-3$ is achievable, but $n-2$ is never achievable.

A problem of Daykin and Erdős. Daykin and Frankl proved that if there are $(1+o(1))\binom{m}{2}$ edges then $m^{1/n}\to 1$ as $n\to \infty$.

For the first question we need to take $\epsilon>0$ since since if $n$ is even and $m=2^{n/2+1}$ one could take $\mathcal{F}$ to be all subsets of $\{1,\ldots,n/2\}$ together with $\{1,\ldots,n/2\}$ union all subsets of $\{n/2+1,\ldots,n\}$, which produces $2^{n}$ edges.

The third question was answered in the affirmative by Alon and Frankl [AlFr85], who proved that, for every $k\geq 1$, if $m=2^{(\frac{1}{k+1}+\delta)n}$ for some $\delta>0$ then the number of edges is \[< \left(1-\frac{1}{k}\right)\binom{m}{2}+O(m^{2-\Omega_k(\delta^{k+1})}).\] They also answer the second question in the negative, noting that if $\mathcal{F}$ is the family of sets which either intersect $\{n/2+1,\ldots,n\}$ in at most $1$ element or intersect $\{1,\ldots,n/2\}$ in at least $n/2-1$ elements then $m \gg n2^{n/2}$ and there are at least $2^{-5}\binom{m}{2}$ edges.

Finally, an affirmative answer to the first question follows from Theorem 1.4 and Corollary 1.5 of Alon, Das, Glebov, and Sudakov [ADGS15].

In other words, this problem asks to determine the chromatic number of the Kneser graph. This would be best possible: if $n=kr-1+(t-1)(k-1)$ then decomposing $[n]$ as one set $X_1$ of size $kr-1$ and $t-1$ sets $X_2,\ldots,X_{t}$ of size $k-1$, a colouring without $k$ pairwise disjoint edges is given colouring all subsets of $X_0$ in colour $1$ and assigning an edge with colour $2\leq i\leq t$ if $i$ is minimal such that $X_i$ intersects the edge.

When $k=2$ this was conjectured by Kneser and proved by Lovász [Lo78]. The general case was proved by Alon, Frankl, and Lovász [AFL86].

Related to [536] and [856]. In [Er70] Erdős asks this in the equivalent formulation with intersection replaced by union.

This is sometimes known as the weak sunflower problem (see [20] for the strong sunflower problem).

When $k=3$ this is strongly connected to the cap set problem (finding the maximal size of subsets of $\mathbb{F}_3^n$ with no three-term arithmetic progressions), as observed by Alon, Shpilka, and Umans [ASU13]). Naslund and Sawin [NaSa17] have proved that \[m(n,3) \leq (3/2^{2/3})^{(1+o(1))n}.\]

In other words, the hypergraph does not have Property B. Property B means that there is a set $S$ which intersects all edges and yet does not contain any edge.

It is known that $m(2)=3$, $m(3)=7$, and $m(4)=23$. Erdős proved \[2^n \ll m(n) \ll n^2 2^n\] (the lower bound in [Er63b] and the upper bound in [Er64e]). Erdős conjectured that $m(n)/2^n\to \infty$, which was proved by Beck [Be77], who proved $m(n)\gg (\log n)2^n$, and later [Be78] improved this to \[n^{1/3-o(1)}2^n \ll m(n).\] Radhakrishnan and Srinivasan [RaSr00] improved this to \[\sqrt{\frac{n}{\log n}}2^n \ll m(n).\] Pluhar [Pl09] gave a very short proof that $m(n) \gg n^{1/4}2^n$.

A conjecture of Erdős and Sós. The classic finite geometry construction shows that $t=n$ is possible. A theorem of Erdős and de Bruijn [dBEr48] states that $t\geq n$.

In [Er82e] Erdős writes that he and Sós proved some special cases of this and the full conjecture was proved by Wilson, but I cannot find either reference.

In general, one can ask what the possible values of $t$ are, for a given $n$.