A k-uniform hypergraph N = (X. B) of order n is a family of k-subsets B of an n-set X. A k-uniform hypergraph 7--L = (X. B) is disjoint union-free (DUF) if all disjoint pairs of elements of B have distinct unions; that is, if for every A, B, C, D E B. A fl B = C f1 D = 0 and A U B =CUD implies {A. B} = {C, D}. DUF families of maximum size have been studied by Erdos and Fiiredi. and in the case k = 3 this maximum size has been conjectured to equal (z). In this thesis, we study DUF 3-uniform hypergraphs with the main goals of presenting evidence to support this conjecture and studying the structures that have conjectured maximum size.
If each pair of distinct elements of X is covered exactly A times in B then we call N = (X, B) an (n. k. A)-design. Using a blend of graph- and design-theoretic techniques, we study the DUF (n,. 3. 3)-designs that are the conjectured unique structures having maximum size. Central results of this thesis include substantially improving lower bounds on the maximum size for a large class of n. giving conditions on pair coverage in a DUF 3-uniform hypergraph that force an (n., 3, 3)-design, and providing constructions for DUF 3-uniform hypergraphs from families of DUF hypergraphs with smaller orders.
Let. N = (X, B) be a DUF k-uniform hypergraph with the property that 7-t U {E} is not DUF for any k-subset E of X not already in H. Then N is maximally DUF. We introduce the problem of finding the minimum size of maximally DUF families and provide bounds on this quantity for k = 3.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1868 |
| Date | January 2006 |
| Creators | Howard, Leah |
| Contributors | Dukes, Peter |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0305 seconds