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 dG(X, Y ) = |E[X, Y ]|/(|X||Y |) where E[X, Y ] denotes the set of edges {x, y} ∈ E with x ∈ X and y ∈ Y . We say the pair (X, Y ) is ε-regular if all subsets XI ⊆ X and Y I ⊆ Y satisfying |XI| > ε|X| and |Y I| > ε|Y | also satisfy |dG(XI, Y I) − dG(X, Y )| < ε.
The Regularity Lemma states that, for all ε > 0, all large n-vertex graphs G = (V, E) admit a partition V = V1 ∪ · · · ∪ Vt, where t = t(ε) depends on ε but not on n, so that all but εt2 pairs (Vi, Vj), 1 ≤ i < j ≤ t, are ε-regular. While Szemere´di’s original proof demonstrates the existence of such a partition, it gave no method for (efficiently) constructing such partitions. Alon, Duke, Lefmann, Ro¨dl, and Yuster [1, 2] showed that such partitions can be constructed in time O(M (n)), where M (n) is the time needed to multiply two n × n {0, 1}-matrices over the integers. Kohayakawa, Ro¨dl, and Thoma [17, 18] improved this time to O(n2).
The Regularity Lemma can be extended to k-uniform hypergraphs, as can algorithmic for- mulations thereof. The most straightforward of these extends the concepts above to k-uniform hypergraphs H = (V, E) in a nearly verbatim way. Let ∅ /= X1, . . . , Xk ⊂ V be pairwise disjoint subsets, and let E[X1, . . . , Xk] denote the set of k-tuples {x1, . . . , xk} ∈ E satisfying x1 ∈ X1, . . . , xk ∈ Xk. We define the density of (X1, . . . , Xk) as
dH(X1, . . . , Xk) = |E[X1, . . . , Xk]| / |X1| · · · |Xk|.
We say that (X1, . . . , Xk) is ε-regular if all subsets XiI ⊆ Xi, 1 ≤ i ≤ k, satisfying |XiI| > ε|Xi| also satisfy
|dH (X1I , . . . , XkI ) − dH (X1, . . . , Xk)| < ε.
With these concepts, Szemeredi’s original proof can be applied to give that, for all integers k ≥ 2 and for all ε > 0, all n-vertex k-uniform hypergraphs H = (V, E) admit a partition V = V1 ∪· · ∪ Vt, where t = t(k, ε) is independent of n, so that all but εtk many k-tuples (Vi1 , . . . , Vik) are ε-regular, where 1 ≤ i1 < · · · < ik ≤ t. Czygrinow and Ro¨dl [4] gave an algorithm for such a regularity lemma, which in the context above, runs in time O(n2k−1 log5 n).
In this dissertation, we consider regularity lemmas for 3-uniform hypergraphs. In this setting, our first main result improves the algorithm of Czygrinow and Ro¨dl to run in time O(n3), which is optimal in its order of magnitude. Our second main result shows that this algorithm gives a stronger notion of regularity than what is described above, where this stronger notion is described in the course of this dissertation. Finally, we discuss some ongoing applications of our constructive regularity lemmas to some classical algorithmic hypergraph problems.
| Identifer | oai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-9166 |
| Date | 25 June 2019 |
| Creators | Theado, John |
| Publisher | Scholar Commons |
| Source Sets | University of South Flordia |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Graduate Theses and Dissertations |
| Rights | default |
Page generated in 0.0021 seconds