On union-closed families. I (Q5906309): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jcta.1998.2888 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2072336136 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4320677 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Union-closed families / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4204156 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:47, 28 May 2024
scientific article; zbMATH DE number 1236154
Language | Label | Description | Also known as |
---|---|---|---|
English | On union-closed families. I |
scientific article; zbMATH DE number 1236154 |
Statements
On union-closed families. I (English)
0 references
2 August 1999
0 references
A family \(F\) of sets is called a UC-family if \(X\cup Y\in F\) whenever \(X\) and \(Y\) belong to \(F\). If, in addition, all the members of \(F\) are finite and non-empty, \(F\) is not a chain, the maximal element \(S\) of \(F\) is the union of \(F\setminus\{S\}\), and \(F\) has at least two minimal elements then \(F\) is said to be a \(\text{UC}^*\)-family. Let \(\text{MGS}(F)\) be the family of members of \(F\) which cover (in the poset of members of \(F\), ordered by inclusion) at most one element. Let \(F\) be a \(\text{UC}^*\)-family with maximal element \(S\) and with \(\text{MGS}(F)=\{A_1, \dots, A_n\}\). The dual \(F^*\) of \(F\) is defined to be the smallest UC-family of subsets of \(\{1, \dots,n\}\) which contains all sets \(\{i\mid x\in A_i\}\), where \(x\in S\). The authors prove the following result: Let \(F\) be a \(\text{UC}^*\)-family. Then there exists some \(x\) contained in at least half the members of \(F\) or there exists some \(i\) contained in at least half the members of \(F^*\). See also the review below.
0 references
union-closed family
0 references
Frankl's conjecture
0 references
dual family
0 references
minimum generating set
0 references