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


1 Answer 1


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.


You must log in to answer this question.

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