Asymptotic solution of a Turán-type problem (Q2276984)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic solution of a Turán-type problem |
scientific article |
Statements
Asymptotic solution of a Turán-type problem (English)
0 references
1990
0 references
Let f(n,k) be the maximum number of edges in a 2k-uniform hypergraph on n vertices which does not contain edges of the form \(A\cup B\), \(A\cup C\), \(B\cup C\) where A, B and C are disjoint k-element sets. The following theorem (related to a problem of B. Bollabás) is proved: \[ (\frac{1}{2}+\frac{c}{n^ 2})/\left( \begin{matrix} n\\ 2k\end{matrix} \right)<f(n,k)<(\frac{1}{2}+\frac{2k}{n-4k})\left( \begin{matrix} n\\ 2k\end{matrix} \right), \] where \(c=c(k)>0\) is a constant. Finally the structure of an extremal hypergraph is conjectured.
0 references
extremal set problem
0 references
symmetric difference
0 references
excluded subgraph
0 references
maximum number of edges
0 references
uniform hypergraph
0 references
extremal hypergraph
0 references