Show simple item record

dc.contributor.authorWang, Richard M.
dc.date.accessioned2020-08-28T09:25:43Z
dc.date.created2019-05
dc.date.issued2019-08-23
dc.date.submitted2019
dc.identifier.citationWang, Richard M. 2019. Applications of flag algebras in extremal graph theory. Bachelor's thesis, Harvard College.
dc.identifier.urihttps://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37364588*
dc.description.abstractWe present an introduction to the theory of flag algebras, a framework under which computer-assisted proofs in asymptotic extremal combinatorics may be derived. We develop the theory of flag algebras for simple graphs and demonstrate how classical problems in extremal graph theory can be proved using flag algebras. We demonstrate the semidefinite method, an algorithm which allows us to derive proofs in extremal graph theory in an almost mechanical manner. Specifically, we will focus on using the semidefinite method to bound Turan densities. In addition, we discuss the limitations of this approach and heuristics which improve its performance. We then consider the use of flag algebras in tackling several difficult problems in graph theory. Namely, we present a proof of the Erd¨os pentagon problem, which asks for the maximum density of pentagons in a triangle-free graph; we give a exposition on how flag algebras have been used to bound Ramsey numbers; we describe the methodology used to prove a case of a conjecture on permutations due to Myers [Mye02]. We also derive Tur´an densities for 4- and 5-uniform hypergraphs, many of which are novel to this thesis.
dc.description.sponsorshipComputer Science
dc.description.sponsorshipComputer Science
dc.format.mimetypeapplication/pdf
dc.language.isoen
dash.licenseLAA
dc.titleApplications of flag algebras in extremal graph theory
dc.typeThesis or Dissertation
dash.depositing.authorWang, Richard M.
dc.date.available2020-08-28T09:25:43Z
thesis.degree.date2019
thesis.degree.grantorHarvard College
thesis.degree.grantorHarvard College
thesis.degree.levelUndergraduate
thesis.degree.levelUndergraduate
thesis.degree.nameAB
thesis.degree.nameAB
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.departmentComputer Science
dash.identifier.vireo
dash.author.emailrichtripled@gmail.com


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record