𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Density of union-closed families

✍ Scribed by Piotr Wójcik

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
425 KB
Volume
105
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

W6jcik, P., Density of union-closed families, Discrete Mathematics 105 (1992) 259-267. Two theorems related to Frankl's conjecture about union-closed families are proved. The first one states how small the sum of degrees in an m-element set may be. Our second result deals with the smallest densities of families generated by sets of equal size. Here density means the ratio of the average element degree to the family's size, and the element degree is the number of sets containing that element.

p(g) = Lv d(x) ISI -WI .

(We assume throughout the paper that 9# 0 and 9# {O}.) Note that p(S) can be interpreted as the ratio of the average set size in 9 to the size of the largest

📜 SIMILAR VOLUMES

Union-closed families of sets
Union-closed families of sets
✍ Piotr Wójcik 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 532 KB

We use a lower bound on the number of small sets in an idea1 to show that for each unionclosed family of n sets there exists an element which belongs to at least of them, provided n is large enough.

On Union-Closed Families, I
On Union-Closed Families, I
✍ Robert T. Johnson; Theresa P. Vaughan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 174 KB

A union closed family A is a finite family of sets such that the union of any two sets in A is also in A. The conjecture under consideration is Conjecture 1: For every union closed family A, there exists some x contained in at least half the members of A. We study the structure of such families (as

On Union-Closed Families, I
On Union-Closed Families, I
✍ Robert T. Johnson; Theresa P. Vaughan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 93 KB
The reduction of graph families closed u
The reduction of graph families closed under contraction
✍ Paul A. Catlin 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 633 KB

Let 5~ be a family of graphs. Suppose there is a nontrivial graph H such that for any supergraph G of H, G is in 5 e if and only if the contraction G/H is in 5g. Examples of such an 0~: graphs with a spanning closed trail; graphs with at least k edge-disjoint spanning trees; and k-edge-connected gra