Conference abstracts

Session B2 - Graph Theory and Combinatorics - Semi-plenary talk

July 13, 14:30 ~ 15:20 - Room B7

Stability and Exactness Results from Flag Algebra Calculations

Oleg Pikhurko

University of Warwick, United Kingdom   -   o.pikhurko@warwick.ac.uk

Flag algebras provide a powerful framework for proving asymptotic inequalities between the possible densities of fixed subgraphs in a large graph. We develop general methods for establishing more refined results (namely, stability as well as exact inequalities) from flag algebra calculations and apply them to concrete examples (Turan function, inducibility problem, etc). In fact, some of our sufficient conditions are stated in a way that allows automatic verification by a computer. This gives a unifying way to obtain computer-assisted proofs of some known and new results.

Joint work with Jakub Sliacan (The Open University, UK) Kostas Tyros (KoƧ University, Turkey).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.