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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.