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.

Winter 2013 Schedule