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.\]
Is it true that \[f(n) \ll n?\]
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)$.
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\}$.
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 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?
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].
Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, \[F(n,\alpha)\sim c_\alpha \log n\] for some constant $c_\alpha$.
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 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.
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.
Solved by Kleitman [Kl71], who proved \[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]
Resolved by Kleitman [Kl69], who proved that the number of such families is \[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]
See also [395].
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].
If the sets $A_x$ are closed and have measure $<1$, then must there exist an independent set of size $3$?
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.
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.\]
Must there exist some set $B$ such that $B\cap A_i\neq \emptyset$ and $\lvert B\cap A_i\rvert \ll_c 1$ for all $i$?
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.
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?
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.
Estimate $T(n,r)$ for $r\geq 2$. In particular, is it true that for every $\epsilon>0$ there exists $\delta>0$ such that for all $\epsilon n<r<(1/2-\epsilon) n$ we have \[T(n,r)<(2-\delta)^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].
That is, can one find a family of $\binom{n}{k}\binom{k}{r}^{-1}$ many subsets of $\{1,\ldots,n\}$, all of size $k$, such that any $A\subseteq \{1,\ldots,n\}$ of size $r$ is contained in exactly one set in the family?
A finite projective plane of order $n$ is a collection of subsets of $\{1,\ldots,n^2+n+1\}$ of size $n+1$ such that every pair of elements is contained in exactly one set.
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].
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.
Are there necessary and sufficient conditions for $(X_i)$ to be block-compatible?
Is there some constant $c>0$ such that for all large $n$ there are \[\geq \exp(c n^{1/2}\log n)\] many block-compatible sequences for $\{1,\ldots,n\}$?
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].
Prove that there are at most \[\exp(O(n^{1/2}))\] many line-compatible sequences.
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].
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$.
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).
How large must $n$ be (as a function of $r$) to ensure that there is such a family which achieves $n-3$ distinct sizes of sets?
Is it true that, if $\epsilon>0$ and $n$ is sufficiently large, whenever $m\leq (2-\epsilon)2^{n/2}$ the graph $G_\mathcal{F}$ has $<2^{n}$ many edges?
Is it true that if $G_{\mathcal{F}}$ has $\geq cm^2$ edges then $m\ll_c 2^{n/2}$?
Is it true that, for any $\epsilon>0$, there exists some $\delta>0$ such that if there are $>m^{2-\delta}$ edges then $m<(2+\epsilon)^{n/2}$?
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].
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].
Estimate $m(n,k)$, or even better, give an asymptotic formula.
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}.\]
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$.
Is it true that if $t>n$ then $t\geq n+p$?
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$.