Back to search

University of South Florida

On Algorithmic Fractional Packings of Hypergraphs

Abstract

dc:description

Let 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 × 7

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/4029

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dizona, Jill. On Algorithmic Fractional Packings of Hypergraphs. Dissertation thesis, University of South Florida, 2012. https://digitalcommons.usf.edu/etd/4029