Logo
All Random Solved Random Open
1 solved out of 5 shown (show only solved or open)
SOLVED
For any $g\geq 2$, if $n$ is sufficiently large and $\equiv 1,3\pmod{6}$ then there exists a 3-uniform hypergraph on $n$ vertices such that
  • 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.
Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].
OPEN
What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.
A problem of Turan. Turan 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].
OPEN
Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergraph on $m$ vertices then there must be some monochromatic copy of the complete $r$-uniform hypergraph on $n$ vertices.

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

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

See also the entry in the graphs problem collection.

OPEN
Let $F(n,\alpha)$ denote the largest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha \binom{\lvert X\rvert}{2}$ many edges of each colour.

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

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.

OPEN - $500
Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the $3$-uniform hypergraph on $n$ vertices.

Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]

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.