# Turan numbers of r-partite hypergraphs

Let $$H$$ be a balanced $$r$$-partite $$r$$-uniform hypergraph with $$nr$$ vertices. (Each part of this hypergraph consists of $$n$$ vertices; every hyperedge has exactly one vertex in each part.) Denote a complete balanced $$r$$-partite $$r$$-uniform hypergraph with $$nr$$ vertices as $$K_{n}^r$$.

Question: What is the maximum number of hyperedges in a hypergraph $$H$$, if it doesn't contain a copy of $$K_{l}^r$$?

I know that there is a theorem by Erdős ("On extremal problems of graphs and generalized graphs", 1964), which states that if an $$r$$-uniform hypergraph doesn't contain a copy of $$K_{l}^r$$, then it can't have more than $$n^{r-1/l^{r-1}}$$ hyperedges. This theorem gives a good bound for the case $$l^{r-1}=o(\log n)$$. But I'm interested in a bound for $$l=n^{\varepsilon}$$. This bound should probably have a form $$n^{r}-f(n, r, l)$$, where $$f(n, r, l)=o(n^r)$$.

Here is a construction for $$r = 2$$ and $$l = \Omega(n^{3/4})$$ with $$n^2 - O(n^{3/2})$$ edges. You can further extend the construction for $$r > 2$$, which I omit here. However I do not know how to deal with smaller $$l$$, for example, $$l \approx n^{1/2}$$.

Taking the complement (with respect to a complete $$r$$-graph) of the graph in your question, the question itself is equivalent to the following one:

Equivalent question: What is the minimum number of edges in an $$n$$ by $$n$$ bipartite graph with parts $$P$$ and $$L$$ such that every $$n^\varepsilon$$-subset of $$P$$ has at least $$n - O(n^\varepsilon)$$ neighbors in $$L$$?

When $$\varepsilon = 3/4$$, the minimum number of edges in the above question is $$O(n^{3/2})$$. Here is how to construct such a graph.

Let $$P$$ and $$L$$ be the points and lines in the projective plane $$PG(2,q)$$ over $$\mathbb{F}_q$$, and let the bipartite graph be the point-line incidence graph. In this case the number of vertices $$n = q^2 + q + 1$$ and the number of edges is $$n(q+1) \approx n^{3/2}$$. We want to understand the smallest number of the neighbors of $$l$$ points in $$P$$. This is known as the isoperimetric problem in $$PG(2,q)$$.

In The isoperimetric problem in finite projective planes by Harper and Hergert, the problem is solved precisely when $$l$$ is of the form $$1 + (m-1)(q+1)$$, and there exists $$l$$ points (known as a maximal $$(l,m)$$-arc) such that no $$m+1$$ points of the the arc lie on the same line. When $$q$$ is a power of $$2$$ and $$m \mid q$$, a maximal $$(l, m)$$-arc exists (see https://en.wikipedia.org/wiki/Maximal_arc).

Thus take $$q = 2^{2r}$$ and $$m = 2^r$$. We know that the smallest number of neighbors of $$l := 1+(m-1)(q+1) \approx n^{3/4}$$ points in $$P$$ is at least $$l(q+1)/m \approx n - n^{3/4}$$ given by a maximal $$(l, m)$$-arc.

Acknowledgment: I benefited a lot from discussing the problem with Ryan Alweiss.