Turán density of an unbalanced complete $r$-partite $r$-graph

Question

In a survey by Füredi and Simonovits called "The history of degenerate (bipartite) extremal graph problems," Theorem 10.5 states the following:

Let $\mathcal K = K^{(r)}(a_1, \dots, a_r)$ be the complete $r$-partite $r$-graph with vertex classes of sizes $a_1, \dots, a_r$, with $|a_1| = t$. There exists a value $m = O(n^{r-{1}/{t^{r-1}}})$ such that every $r$-graph on $n$ vertices with $m$ edges contains a copy of $\mathcal K$.

It is not clear from the notation whether or not the host graph must also be $r$-partite, but for asymptotic results, this typically does not matter. My main concern is that Füredi and Simonovits cite the paper "On some extremal problems in graph theory" by Erdős (1965, Israel J. Math.), but the paper that they cite doesn't actually contain anything about hypergraphs. There is another paper by Erdős called "On extremal problems of graphs and generalized graphs" (1964, Israel J. Math) which deals with this same problem, but in the special case that $a_1 = \dots = a_r$. However, directly applying the method from this second paper to the general problem seems to give $r - \frac{1}{\prod_{i = 1}^{r-1} a_i}$ in the exponent of $n$. This brings me to my questions.

1. Is this Theorem 10.5 even true?
2. If this theorem is true, what is the correct reference for the result?

I'd be grateful for anyone's help. Thank you.

Answer 1

I don't know if this helps, but here's a modern probabilistic proof of this fact.

We show the contrapositive, that if $\mathcal{H}$ does not include $\mathcal{K}$ then it does not have too many edges. By considering a random r-partition $V_1\sqcup \ldots \sqcup V_r$ of the ground set, up to the loss of a constant multiplicative factor we may assume our hygraph $\mathcal{H}$ is $r$-partite with all parts having sizes within a constant factor of $n$.

Let $X_i$ be a uniformly random element of $V_i$, we want to show that $\Pr(X_1\ldots X_r\in \mathcal{H})=O(n^{-\frac{1}{\prod_{i=1}^{r-1} a_i}})$.

We use the following decoupling inequality (which is an immediate corollary of Jensen's inequality, I saw a version of this in Costello-Tao-Vu although I believe that it is an older observation): if $E(x,y)$ is an event, $X_1,\ldots,X_k$ are i.i.d. copies of a random variable $X$ (taking values in the domain of the first input of $E$), and $Y$ is another random variable (taking values in the domain of the second input), then $\Pr(E(X,Y))\le \Pr(\bigwedge_{i=1}^kE(X_i,Y))$.

So we let $X_i^{(1)},X_i^{(2)},\ldots,X_i^{(a_i)}$ be i.i.d. copies of $X_i$ for $i=1,\ldots,r-1$. Applying the decoupling inequality repeatedly we have

$\Pr(X_1\ldots X_r\in \mathcal{H})\le \Pr(\bigwedge_{j_1,\ldots,j_{r-1}} X_1^{(j_1)}X_2^{(j_2)}\ldots X_{r-1}^{(j_{r-1})}X_r\in \mathcal{H})^{\frac{1}{\prod_{i=1}^{r-1} a_i}}$.

Inspect the $X_i^{(j_i)}$ for $1\le i \le r-1$ and $1 \le j_i \le a_i$. The probability that for some fixed $i$ there's a collision $X_i^{(j)}=X_i^{(k)}$ is $O(n^{-1})$ because each part has size within a constant factor of $n$. On the other hand, if there is no collision, then there are at most $a_r-1$ values of $X_r$ such that all of the necessary edges are in the hypergraph by the forbidden $\mathcal{K}$ condition, so the probability is $O(n^{-1})$ that $X_r$ is such a value. Combining these we see that $\Pr(\bigwedge_{j_1,\ldots,j_{r-1}} X_1^{(j_1)}X_2^{(j_2)}\ldots X_{r-1}^{(j_{r-1})}X_r\in \mathcal{H})=O(n^{-1})$ and the result follows.