Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650411 | Discrete Mathematics | 2008 | 4 Pages |
Abstract
A family FF of k-subsets of an n-set X is disjoint union-free (DUF) if all disjoint pairs of elements of FF have distinct unions; that is, if for every A,B,C,D∈FA,B,C,D∈F, A∩B=C∩D=∅A∩B=C∩D=∅ and A∪B=C∪DA∪B=C∪D implies {A,B}={C,D}{A,B}={C,D}. DUF families of maximum size have been studied by Erdös and Füredi. Let FF be DUF with the property that F∪{E}F∪{E} is not DUF for any k-subset E of X not already in FF. Then FF is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for k=3k=3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter Dukes, Lea Howard,