Article ID Journal Published Year Pages File Type
4650411 Discrete Mathematics 2008 4 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,