Small maximally disjoint union-free families

Abstract: A family of k-subsets of an n-set X is disjoint union-free (DUF) if all disjoint pairs of elements of have distinct unions; that is, if for every , and implies . DUF families of maximum size have been studied by Erdös and Füredi. Let be DUF with the property that is not DUF for any k-subset E of X not already in . Then is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for . [Copyright &y& Elsevier]