Set systems with few disjoint pairs (Q1878795)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Set systems with few disjoint pairs
scientific article

    Statements

    Set systems with few disjoint pairs (English)
    0 references
    0 references
    0 references
    8 September 2004
    0 references
    An old theorem of \textit{P. Frankl} [J. Comb. Theory, Ser. A 22, 249--251 (1977; Zbl 0363.05010)] and \textit{R. Ahlswede} [J. Comb. Theory, Ser. B 28, 164--167 (1980; Zbl 0441.05036)] states that any set system with at least \(\left | [n]^{\geq r} \right | \) elements has at least as many disjoint pairs as the set system \([n]^{\geq r}.\) This paper gives a new proof of this fact as well as a fairly good lower bound on the minimum number of disjoint pairs as a function of the size of a general system. The main tool of the proof is the new notion of a fractional set system.
    0 references
    intersecting families
    0 references
    Kneser graph
    0 references
    Erdős-Ko-Rado theorem
    0 references
    fractional set system
    0 references

    Identifiers