#### Graduation Year

2012

#### Document Type

Dissertation

#### Degree

Ph.D.

#### Degree Granting Department

Mathematics and Statistics

#### Major Professor

Brendan Nagle

#### Keywords

extremal combinatorics, fractional packings, linear hypergraphs, regularity

#### Abstract

Let F_{0} be a fixed k-uniform hypergraph, and let H be a given k-uniform hypergraph on n vertices. An F_{0}-packing of H is a family *F* of edge-disjoint copies of F_{0} which are subhypergraphs in H. Let n_{F0}(H) denote the maximum size |*F*| of an F_{0}-packing *F* of H. It is well-known that computing n_{F0}(H) is NP-hard for nearly any choice of F_{0}.

In this thesis, we consider the special case when F_{0} is a linear hypergraph, that is, when no two edges of F_{0} overlap in more than one vertex. We establish for *z* > 0 and n &ge n_{0}(*z*) sufficiently large, an algorithm which, in time polynomial in n, constructs an F_{0}-packing *F* of H of size |*F*| ≥ n_{F0}(H) - *z*n^{k}.

A central direction in our proof uses so-called fractional F_{0}-packings of H which are known to approximate n_{F0}(H). The driving force of our argument, however, is the use and development of several tools within the theory of hypergraph regularity.

#### Scholar Commons Citation

Dizona, Jill, "On Algorithmic Fractional Packings of Hypergraphs" (2012). *Graduate Theses and Dissertations.*

http://scholarcommons.usf.edu/etd/4029