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
    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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references