2
$\begingroup$

$\DeclareMathOperator\ex{ex}$We write $K_{2,\dots,2}^{(r)}$ to denote the $r$-uniform hypergraph with vertex set $\{1,2\}\times\{1,\dots,r\}$ and hyperedge set $\{(1,1),(1,2)\}\times \{(2,1),(2,2)\} \dots \times \{(r,1),(r,2)\}$.

For integer $n$, the Turan number $\ex(n,K_{2,\dots,2}^{(r)})$ denotes the maximum number of hyperedges in a $n$-vertex $r$-uniform hypergraph $H$ which does not have $K_{2,\dots,2}^{(r)}$ as a subhypergraph.

Reading some papers from the 90's, I gather that for $r\ge 3$, the bounds $$n^{r-r/(2^r-1)}\ll \ex(n,K_{2,\dots,2}^{(r)}) \le n^{r-1/2^{r-1}}$$were known. I believe the lower bound is by the probabilistic deletion method, while the upper bound is by induction.

Does this remain the state of the art? I'm particularly curious about $r=3$.

$\endgroup$

1 Answer 1

3
$\begingroup$

A recent paper by Conlon, Pohoata and Zakharov provides new lower bounds and a survey on the history of the problem. It seems that the upper bound is the state of the art. Now we know that for every $r \geq 2$ there are lower bounds better than the one obtained from probabilistic deletion. In particular for $r =3$ it holds that $ex(n, K^{(3)}_{2,2,2}) = \Omega(n^{8/3})$ (which was in fact already proven by Katz, Krop and Maggioni before).

Conlon, David; Pohoata, Cosmin; Zakharov, Dmitriy, Random multilinear maps and the Erdős box problem, Discrete Anal. 2021, Paper No. 17, 8 p. (2021). ZBL1482.05167.

Katz, Nets Hawk; Krop, Elliot; Maggioni, Mauro, Remarks on the box problem, Math. Res. Lett. 9, No. 4, 515-519 (2002). ZBL1031.42018.

$\endgroup$
1
  • $\begingroup$ ah great, I had forgotten this paper! $\endgroup$ Commented Sep 22, 2022 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .