Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

The Szemerédi Regularity Lemma

Everett, Emma (2017) The Szemerédi Regularity Lemma. Master's Thesis, University of Pittsburgh. (Unpublished)

Primary Text

Download (604kB) | Preview


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Everett, Emmaemp91@pitt.eduemp91
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairWheeler, Jeffreyjwheeler@pitt.edujwheeler
Committee MemberRubin, Jonathanjonrubin@pitt.edujonrubin
Committee MemberTrenchea, Catalintrenchea@pitt.edutrenchea
Committee MemberSokolov, Yuryysokolov@pitt.eduysokolov
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


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item