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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1600980
Language Label Description Also known as
default for all languages
No label defined
    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