Everett, Emma
(2017)
The Szemerédi Regularity Lemma.
Master's Thesis, University of Pittsburgh.
(Unpublished)
Abstract
The Szemerédi Regularity Lemma is a deep result in graph theory which roughly states that large, dense graphs can be approximated by random graphs. The lemma is most helpful in proofs where it may be hard to prove a result for a large graph but could be proven for a smaller random graph. This paper gives an overview of the lemma including relevant definitions and the proof of the theorem. The main importance of the theorem can be found in applications in several disciplines of mathematics such as extremal graph theory, Ramsey theory, and number theory. The main focus of the paper is to demonstrate the use of the lemma in several applications including the Triangle Removal Lemma, Roth's Theorem, the Erdős-Stone theorem and more.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
15 June 2017 |
| Date Type: |
Publication |
| Defense Date: |
10 April 2017 |
| Approval Date: |
15 June 2017 |
| Submission Date: |
13 April 2017 |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Number of Pages: |
66 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Dietrich School of Arts and Sciences > Mathematics |
| Degree: |
MS - Master of Science |
| Thesis Type: |
Master's Thesis |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
Szemerédi Regularity Lemma, regularity, density, equipartition, reduced graph, arithmetics progressions |
| Date Deposited: |
15 Jun 2017 22:25 |
| Last Modified: |
15 Jun 2017 22:25 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/31448 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}