- every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner triple system) and
- for any $2\leq j\leq g$ any collection of $j$ edges contains at least $j+3$ vertices.
See also [712] for the general case.
Prove that, for $r\geq 3$, \[\log_{r-1} R_r(n) \asymp_r n,\] where $\log_{r-1}$ denotes the $(r-1)$-fold iterated logarithm. That is, does $R_r(n)$ grow like \[2^{2^{\cdots n}}\] where the tower of exponentials has height $r-1$?
Prove that, for every $0\leq \alpha\leq 1/2$, \[F(n,\alpha)\sim c_\alpha\log n\] for some constant $c_\alpha$ depending only on $\alpha$.
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].
Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]
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}.\]
See also [500] for the case $r=3$ and $k=4$.
In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.
Is every $r$-hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$, no two of which share a $K_r^r$?
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).
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].
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\}$.
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$.
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.
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.
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$.
Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.
What is $A_3$?
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$.