On applications of Szemerédi's regularity lemma
Abstract/Contents
- Abstract
- Szemeredi's regularity lemma is an important and powerful tool in graph theory. One of its prevalent application is the graph removal lemma, which has numerous applications to extremal problems for graphs and hypergraphs, additive combinatorics, discrete geometry, and theoretical computer science. In this thesis, we initiate and prove a new removal lemma with respect to a stronger metric on graphs, which is a strengthening of the usual graph removal lemma. We also prove a new application of the regularity lemma. The Ramsey number r(H) of a graph H is the minimum integer n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. Determining the Ramsey number for all graphs is a famously difficult question. A more general question is to study the minimum total number of monochromatic copies of H over all two-colorings of Kn. When n = r(H), this quantity is referred to as the threshold Ramsey multiplicity of H. Addressing a problem of Harary and Prins forty years ago, we proved the first quantitative sharp bound for cycles and paths. This thesis describes the work for path and even cycles. Although the regularity lemma is powerful, a notable drawback is that applications of the regularity lemma will result in very weak quantitative estimates. One important application of the regularity lemma is the field of property testing, whose goal is to very quickly distinguish between objects that stratify a certain property from those that are epsilon-far from satisfying that property. Some of the most general results in this area give ``constant query complexity" algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/epsilon, making them impractical. We show by entirely new methods that for permutations property testing, such general results still hold with query complexity only polynomial in 1/epsilon.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Wei, Fan, (Mathematician) | |
|---|---|---|
| Degree supervisor | Fox, Jacob, 1984- | |
| Thesis advisor | Fox, Jacob, 1984- | |
| Thesis advisor | Chatterjee, Sourav | |
| Thesis advisor | Vondrak, Ján, (Mathematician) | |
| Degree committee member | Chatterjee, Sourav | |
| Degree committee member | Vondrak, Ján, (Mathematician) | |
| Associated with | Stanford University, Department of Mathematics. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Fan Wei. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Fan Wei
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...