The Erdős Pentagon Problem

graph theory;extremal graph theory;pentagon problem;flag algebras

Siy, Krisadvisor:Haxell, Penny ; affiliation1:Faculty of Mathematics ; Haxell, Penny ;

University of Waterloo

关键词: flag algebras;    Master Thesis;    graph theory;    extremal graph theory;    pentagon problem;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/14274/1/Siy_Kris.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

The Erdős pentagon problem asks about the maximum number of copies of C_5 that one can find in a triangle-free graph. This problem was posed in 1984, but was not resolved until 2012. In this thesis, we aim to capture the story of solving the pentagon problem as completely as possible. We provide a detailed exposition of the motivation behind and construction of flag algebras, and give a complete solution to the pentagon problem using flag algebra techniques. All known solutions of the pentagon problem to date have been computer-assisted; with the question of whether an elementary solution can be found in mind, we also investigate the pentagon problem and modifications of the problem from different elementary perspectives.