Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs

Dhruv Mubayi ; John Talbot

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/750

Classification : 05D05, 05C15, 05C35, 05C65
Mots-clés : maximumm number of edges, r-uniform hypergraph, t-chromatic hypergraph, Lagrangian of a hypergraph