Michael Burgher’s Thesis Proposal

Date: Friday January 27th, 10:00 am

Location: In person- ACAD-4017, Zoom (email MathStats-Staff@ucdenver.edu for link)

Committee: Stephen Hartke (chair), Florian Pfender (advisor), Steffen Borgwardt, Michael Jacobson, Bernard Lidicky

Title: Thesis Proposal in Extremal Graph Theory, Flag Algebra Applications and Inducibility

Abstract:
Inducibility is a classically studied problem in Extremal Graph Theory. The inducibility of a graph H is



where P (H, G) is the subgraph density of H in G. This was first studied by Pippenger and Golumbic in 1975.
As with all extremal graph theory problems, given a graph, we want to classify all extremal structures in addition to finding the inducibility for a given graph. However, despite being a classically studied problem, the results have been discovered for only a few simple graphs. There is hope that studying triangle-free inducibility (where the extremal structures are limited to triangle-free graphs) will help yield some further results. In 2007, Razborov introduced a new technique called Flag Algebra that has assisted finding solutions in Extremal Graph Theory. Presented in this proposal is an explanation of how Flag Algebra is used to prove triangle-free density for P7 (a path on seven vertices) and some future results we hope to achieve.