Digital Commons Network^™

An Optimal Medium-Strength Regularity Algorithm For 3-Uniform Hypergraphs, John Theado

USF Tampa Graduate Theses and Dissertations

Szemere´di’s Regularity Lemma [32, 33] is an important tool in combinatorics, with numerous appli- cations in combinatorial number theory, discrete geometry, extremal graph theory, and theoretical computer science.

The Regularity Lemma hinges on the following concepts. Let G = (V, E) be a graph and let ∅ /= X, Y ⊂ V be a pair of disjoint vertex subsets. We define the density of the pair (X, Y ) by d_G(X, Y ) = |E[X, Y ]|/(|X||Y |) where E[X, Y ] denotes the …

On Extending Hansel's Theorem To Hypergraphs, Gregory Sutton Churchill

USF Tampa Graduate Theses and Dissertations

For integers $n \geq k \geq 2$, let $V$ be an $n$-element set, and let $\binom{V}{k}$ denote the family of all $k$-element subsets of $V$. For disjoint subsets $A, B \subseteq V$, we say that $\{A, B\}$ {\it covers} an element $K \in \binom{V}{k}$ if $K \subseteq A \dot\cup B$ and $K \cap A \neq \emptyset \neq K \cap B$. We say that a collection $\cC$ of such pairs {\it covers} $\binom{V}{k}$ if every $K \in \binom{V}{k}$ is covered by at least one $\{A, B\} \in \cC$. When $k=2$, covers $\cC$ of $\binom{V}{2}$ were introduced in~1961 by R\'enyi~\cite{Renyi}, where they …