A new perspective on the union-closed sets conjecture. (Q2716014)

From MaRDI portal





scientific article; zbMATH DE number 1600980
Language Label Description Also known as
English
A new perspective on the union-closed sets conjecture.
scientific article; zbMATH DE number 1600980

    Statements

    0 references
    20 July 2005
    0 references
    inclusion-exclusion principle
    0 references
    chain
    0 references
    A new perspective on the union-closed sets conjecture. (English)
    0 references
    More than 20 years old conjecture of \textit{P. Frankl} asserts that every non-empty finite system of finite sets that is closed under unions has a point that is contained in at least half of the sets. The author uses a result of \textit{H.\ Narushima} [J.\ Comb.\ Theory, Ser.\ A 17, 196-203 (1974; Zbl 0289.05013)] to show that every counterexample \({\mathcal S}\) to the conjecture satisfies the identity \(I(\bigcup {\mathcal S})=\sum (-1)^{| {\mathcal T}| -1}I(\bigcap {\mathcal T})\) where \(I\) is the characteristic function and the summation is over all non-empty \({\mathcal T}\subset {\mathcal S}\) (this would be the ordinary PIE) such that \({\mathcal T}\) is a chain (to inclusion) and \(| {\mathcal T}| <| {\mathcal S}| /2\).
    0 references
    0 references

    Identifiers