Back to search

University of South Florida

A Hypergraph Regularity Method for Linear Hypergraphs

Abstract

dc:description

Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and Skokan, by W.T. Gowers, and subsequently, by T. Tao. These extensions have yielded quite a few non-trivial applications to Extremal Hypergraph Theory, Combinatorial Number Theory and Theoretical Computer Science. A main drawback to the hypergraph regularity techniques above is that they are highly technical. In this thesis, we consider a less technical version of hypergraph regularity which more directly generalizes Szemeredi's regularity lemma for graphs. The tools we discuss won't yield all applications of their stronger relatives, but yield still several applications in extremal hypergraph theory (for so-called linear or simple hypergraphs), including algorithmic ones. This thesis surveys these lighter regularity techiques, and develops three applications of them.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Khan, Shoaib Amjad
Contributors dc:contributor
  • Brendan Nagle, Ph.D.
  • Brian Curtin, 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/2042

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

Khan, Shoaib Amjad. A Hypergraph Regularity Method for Linear Hypergraphs. Thesis thesis, University of South Florida, 2009. https://digitalcommons.usf.edu/etd/2042