| Monday, March 25th, 2013 | 4pm-5pm | Burnside 1205 |
Monash University, Melbourne, Australia
Irreducible triangulations of surfaces and an application in
extremal graph theory
Irreducible triangulations are the building blocks of all graphs embedded in a given surface. For each surface there are finitely many irreducible triangulations. This seminar will consist of a friendly introduction to irreducible triangulations, leading to the recent result that every irreducible triangulation of a surface with Euler genus g has at most 13g vertices. Then we will consider the extremal question: what is the maximum number of cliques in an n-vertex graph embedded in a given surface? Irreducible triangulations characterise the extremal graphs for this question, and lead to tight bounds.