On Algorithmic Hypergraph Regularity Open Access

Abstract

Thomason and Chung, Graham and Wilson were the first to systematically study quasi-random graphs and hypergraphs and showed that several properties of random graphs imply each other in a deterministic sense. In particular, they showed that ε-regularity from Szemerédi's regularity lemma is equivalent to their concepts. Over recent years several hypergraph regularity lemmas were established.

In this dissertation, we focus on two regularity lemmas for 3-uniform hypergraphs one due to Gowers, and one due to Haxell, Nagle, and Rödl. Their lemmas are based on different notions of quasirandom hypergraphs and we show that their concepts are in fact equivalent. Since the regularity lemma of Haxell, Nagle, and Rödl is algorithmic, we also obtain an algorithmic version of Gowers' regularity lemma. Further, we use Gowers' analytic approach to the hypergraph regularity lemma to give a more direct proof of the algorithmic version of his regularity lemma.

Table of Contents

1 Introduction

2 Graphs 2.1 Quasirandomness 2.1.1 Basic Definitions and Concepts 2.1.2 Relation of the Concepts 2.2 Regularity Lemma 2.3 Counting Lemma

3 Equivalence Relations of Quasirandomness for 3-uniform Hypergraphs 3.1 Quasirandomness 3.1.1 Basic Definitions and Concepts 3.1.2 The Equivalence of Several Versions of Quasirandomness for 3-uniform Hypergraphs

3.2 Relative quasirandomness 3.2.1 Definitions and Concepts 3.2.2 The Equivalence Statement 3.2.3 Counting Lemmas and Auxiliary Facts 3.2.4 Proof of Theorem 3.10

4 Algorithmic Quasirandom Lemma 4.1 Statement of the Algorithmic Quasirandom Lemma 4.2 Proof of Theorem 4.1 4.2.1 Iteration I 4.2.2 Iteration s 4.3 Proof of Algorithm 4.3 4.3.1 Proof of Algorithm 4.7 4.3.2 Proof of Algorithm 4.8

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Quasirandomness Szemeredi's Regularity Lemma Algorithms Hypergraphs Graphs
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Schacht, Mathias, Humboldt University zu Berlin Duffus, Dwight A, Emory University Gould, Ronald J, Emory University Nagle, Brendan, University of South Florida

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On Algorithmic Hypergraph Regularity ()	2018-08-28 12:52:22 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions