Abstract
dc:descriptionLet F0 be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F0-packing of H is a family F of edge-disjoint copies of F0 which are subhypergraphs in H. Let nF0(H) denote the maximum size |F| of an F0-packing F of H. It is well-known that computing nF0(H) is NP-hard for nearly any choice of F0. In this thesis, we consider the special case when F0 is a linear hypergraph, that is, when no two edges of F0 overlap in more than one vertex. We establish for z > 0 and n &ge n0(z) sufficiently large, an algorithm which, in time polynomial in n, constructs an F0-packing F of H of size |F| ≥ nF0(H) - znk. A central direction in our proof uses so-called fractional F0-packings of H which are known to approximate nF0(H). The driving force of our argument, however, is the use and development of several tools within the theory of hypergraph regularity.
Degree
thesis:*- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics and Statistics
- Grantor
- University of South Florida
- Year dc:date
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Dizona, Jill
- Contributors dc:contributor
-
- Brendan Nagle, Ph.D.
- Jay Ligatti, Ph.D
- Catherine Beneteau, Ph.D.
- Brian W. Curtin, Ph.D.
- Nat˘asa Jonoska, Ph.D.
- Stephen Suen, Ph.D.
Subjects
dc:subject × 7Rights
- Language dc:language
- EN-US
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/4029