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

A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that \[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\] This is probably the truth. The current best upper bound is \[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\] due to Razborov [Ra10].

See also [712] for the general case.

A problem of Erdős, Hajnal, and Rado [EHR65]. A generalisation of [564].

See also the entry in the graphs problem collection.

It is easy to show that, for every $0\leq \alpha\leq 1/2$, \[F(n,\alpha)\asymp_\alpha \log n.\]

Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.

See also [161].

See also the entry in the graphs problem collection.

A special case of [562]. A problem of Erdős, Hajnal, and Rado [EHR65], who prove the bounds \[2^{cn^2}< R_3(n)< 2^{2^{n}}\] for some constant $c>0$.

Erdős, Hajnal, Máté, and Rado [EHMR84] have proved a doubly exponential lower bound for the corresponding problem with $4$ colours.

See also the entry in the graphs problem collection.

Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]. Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq \aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle.

For $n=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1+o(1))n^{3/2}$.

Füredi proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. More generally, Füredi proved that \[f(n;t) \ll \binom{n}{t-1}.\]

Turán proved that, when $r=2$, this limit is \[\frac{1}{2}\left(1-\frac{1}{k-1}\right).\] Erdős [Er81] offered \$500 for the determination of this value for any fixed $k>r>2$, and \$1000 for 'clearing up the whole set of problems'.

See also [500] for the case $r=3$ and $k=4$.

A conjecture of Brown, Erdős, and Sós. The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known as the Ruzsa-Szemerédi problem).

In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.

A conjecture of Erdős and Sauer.

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

Erdős constructed such a hypergraph with cliques of at least $n-\log_*n$ different sizes. For graphs, Spencer [Sp71] constructed a graph which contains cliques of at least $n-\log_2n+O(1)$ different sizes, which Moon and Moser [MoMo65] showed to be best possible.

See also [927].

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

Balogh has observed that this problem is probably misstated by Erdős - indeed, every graph with $5$ vertices spanning $7$ edges contains a graph on $4$ vertices spanning $3$ edges, so the second condition can be dropped.

This problem is then now asking how many edges a $3$-uniform hypergraph can have before it contains $K_4$ minus an edge, and whether the critical edge density is $2/9$. In fact there is a construction of Frankl and Füredi [FrFu84] showing it must be at least $2/7$, which is the conjectured truth (although Turán conjectured before [Er69] that that the edge density was $1/4$, and so likely there is simply a typo in this problem's statement).

Harris has provided the following simple counterexample to the problem as stated: the $3$-uniform graph on $\{1,\ldots,9\}$ with $28$ edges, formed by taking $27$ edges by choosing one element each from $\{1,2,3\},\{4,5,6\},\{7,8,9\}$, and then adding the edge $\{1,2,3\}$.

When $r=2$ it is a classical fact that chromatic number $k$ implies at least $\binom{k}{2}$ edges. Erdős asked for $k$ to be large in this conjecture since he knew it to be false for $r=k=3$, as witnessed by the Steiner triples with $7$ vertices and $7$ edges.

This was disproved by Alon [Al85], who proved, for example, that there exists some absolute constant $C>0$ such that if $r\geq C$ and $k\geq Cr$ then there exists an $r$-uniform hypergraph with chromatic number $\geq k$ with at most \[\leq (7/8)^r\binom{(r-1)(k-1)+1}{r}\] many edges.

In general, Alon gave an upper bound for the minimal number of edges using Turán numbers. Using known bounds for Turán numbers then suffices to disprove this conjecture for all $r\geq 4$. The validity of this conjecture for $r=3$ remains open.

If $m(r,k)$ denotes the minimal number of edges of any $r$-uniform hypergraph with chromatic number $>k$ then Akolzin and Shabanov [AkSh16] have proved \[\frac{r}{\log r}k^r \ll m(r,k) \ll (r^3\log r) k^r,\] where the implied constants are absolute. Cherkashin and Petrov [ChPe20] have proved that, for fixed $r$, $m(r,k)/k^r$ converges to some limit as $k\to \infty$.

In general, determine the largest integer $f(r)$ such that every $r$-uniform hypergraph with chromatic number $3$ has a vertex contained in at least $f(r)$ many edges. It is easy to see that $f(2)=2$ and $f(3)=3$. Erdős did not know the value of $f(4)$.

This was solved by Erdős and Lovász [ErLo75], who proved in particular that there is a vertex contained in at least \[\frac{2^{r-1}}{4r}\] many edges.

A problem of Erdős and Lovász.

They do not specify what is meant by $3$-critical. One definition in the literature is: a hypergraph is $3$-critical if there is a set of $3$ vertices which intersects every edge, but no such set of size $2$, and yet for any edge $e$ there is a pair of vertices which intersects every edge except $e$. Raphael Steiner observes that a $3$-critical hypergraph in this sense has bounded size, so this problem would be a finite computation, and perhaps is not what they meant.

An alternative definition is that a hypergraph is $3$-critical if it has chromatic number $3$, but its chromatic number becomes $2$ after deleting any edge or vertex.

A problem of Erdős and Rosenfeld. This is trivially possible for $k=2$. They were not sure about $k=6$.

This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at this website show that this is false for $3\leq k\leq 8$.

A problem of Erdős and Shelah. The Fano geometry gives an example where there are no two edges which meet in $r-1$ vertices. Are there any other examples?

Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.

A problem of Erdős and Simonovits. It is known that \[A_2 = \left\{ 1-\frac{1}{k} : k\geq 1\right\}.\]

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