Back to search

University of South Florida

An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Theado, John
Contributors dc:contributor
  • Brendan Nagle, Ph.D.
  • Jay Ligatti, Ph.D.
  • Brian Curtin, Ph.D.
  • Natǎsa Jonoska, Ph.D.
  • Theodore Molla, Ph.D.
  • Dmytro Savchuk, Ph.D.

Subjects

dc:subject × 6

Identifiers

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

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

Theado, John. An Optimal Medium-Strength Regularity Algorithm for 3-uniform Hypergraphs. Dissertation thesis, University of South Florida, 2019. https://digitalcommons.usf.edu/etd/7969