Largest size and union of Helly families (Q1322238)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Largest size and union of Helly families
scientific article

    Statements

    Largest size and union of Helly families (English)
    0 references
    0 references
    14 November 1994
    0 references
    A \(k\)-uniform hypergraph is a hypergraph in which all edges have precisely \(k\) vertices. A hypergraph is called intersecting if and only if any two of its edges share a vertex. A \(k\)-uniform hypergraph is called a Helly family if each of its intersecting subhypergraphs has the property that the intersection of all its edges is not empty. The author's conjecture that the union of \(t\) \(k\)-uniform Helly families on sets of \(n\) elements can have at most \(\sum^ t_{i=1} {n-i\choose k-1}\) members is proved for every \(k\) and every \(t= 2k-2\) if \(n\) is sufficiently large with respect to \(k\), and \(\sum^ t_{i=1} {n- i\choose k-1}\) is a best upper bound whenever \(n\geq (t+ 2k- 1)(k- 1)\).
    0 references
    0 references
    0 references
    intersecting hypergraph
    0 references
    \(k\)-uniform hypergraph
    0 references
    Helly family
    0 references