Sparse regularity and relative Szemerédi theorems
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/99060 |
| _version_ | 1826198083958996992 |
|---|---|
| author | Zhao, Yufei |
| author2 | Jacob Fox. |
| author_facet | Jacob Fox. Zhao, Yufei |
| author_sort | Zhao, Yufei |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015. |
| first_indexed | 2024-09-23T10:58:55Z |
| format | Thesis |
| id | mit-1721.1/99060 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:58:55Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/990602019-04-12T14:13:29Z Sparse regularity and relative Szemerédi theorems Zhao, Yufei Jacob Fox. Massachusetts Institute of Technology. Department of Mathematics. Massachusetts Institute of Technology. Department of Mathematics. Mathematics. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015. Cataloged from PDF version of thesis. Includes bibliographical references (pages 171-179). We extend various fundamental combinatorial theorems and techniques from the dense setting to the sparse setting. First, we consider Szemerédi regularity lemma, a fundamental tool in extremal combinatorics. The regularity method, in its original form, is effective only for dense graphs. It has been a long standing problem to extend the regularity method to sparse graphs. We solve this problem by proving a so-called "counting lemma," thereby allowing us to apply the regularity method to relatively dense subgraphs of sparse pseudorandom graphs. Next, by extending these ideas to hypergraphs, we obtain a simplification and extension of the key technical ingredient in the proof of the celebrated Green-Tao theorem, which states that there are arbitrarily long arithmetic progressions in the primes. The key step, known as a relative Szemerédi theorem, says that any positive proportion subset of a pseudorandom set of integers contains long arithmetic progressions. We give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Finally, we give a short simple proof of a multidimensional Szemerédi theorem in the primes, which states that any positive proportion subset of Pd (where P denotes the primes) contains constellations of any given shape. This has been conjectured by Tao and recently proved by Cook, Magyar, and Titichetrakun and independently by Tao and Ziegler. by Yufei Zhao. Ph. D. 2015-09-29T19:00:56Z 2015-09-29T19:00:56Z 2015 2015 Thesis http://hdl.handle.net/1721.1/99060 921851434 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 179 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Zhao, Yufei Sparse regularity and relative Szemerédi theorems |
| title | Sparse regularity and relative Szemerédi theorems |
| title_full | Sparse regularity and relative Szemerédi theorems |
| title_fullStr | Sparse regularity and relative Szemerédi theorems |
| title_full_unstemmed | Sparse regularity and relative Szemerédi theorems |
| title_short | Sparse regularity and relative Szemerédi theorems |
| title_sort | sparse regularity and relative szemeredi theorems |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/99060 |
| work_keys_str_mv | AT zhaoyufei sparseregularityandrelativeszemereditheorems |