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
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.8686308264732361
0 references
0.8681703805923462
0 references
0.8663482069969177
0 references