Extremal Problems for $t$-Partite and $t$-Colorable Hypergraphs

Dhruv Mubayi, John Talbot

Abstract


Fix integers $t \ge r \ge 2$ and an $r$-uniform hypergraph $F$. We prove that the maximum number of edges in a $t$-partite $r$-uniform hypergraph on $n$ vertices that contains no copy of $F$ is $c_{t, F}{n \choose r} +o(n^r)$, where $c_{t, F}$ can be determined by a finite computation.

We explicitly define a sequence $F_1, F_2, \ldots$ of $r$-uniform hypergraphs, and prove that the maximum number of edges in a $t$-chromatic $r$-uniform hypergraph on $n$ vertices containing no copy of $F_i$ is $\alpha_{t,r,i}{n \choose r} +o(n^r)$, where $\alpha_{t,r,i}$ can be determined by a finite computation for each $i\ge 1$. In several cases, $\alpha_{t,r,i}$ is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph.


Full Text: PDF