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 this page instead for the normal view: A new perspective on the union-closed sets conjecture. |
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
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