Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs (Q1010732)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs |
scientific article |
Statements
Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs (English)
0 references
7 April 2009
0 references
Summary: Fix integers \(t \geq r \geq 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}\binom{n}{r} +o(n^r)\), where \(c_{t, F}\) can be determined by a finite computation. We explicitly define a sequence \(F_1, F_2, \dots\) 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}\binom{n}{r} +o(n^r)\), where \(\alpha_{t,r,i}\) can be determined by a finite computation for each \(i\geq 1\). In several cases, \(\alpha_{t,r,i}\) is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph.
0 references
maximumm number of edges
0 references
r-uniform hypergraph
0 references
t-chromatic hypergraph
0 references
Lagrangian of a hypergraph
0 references