Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 09.02.2012 at 12:20 in S1, there is the following noon lecture:

Bounds on the diameter of the flip graph

Maria Saumell

Abstract

Given a combinatorial embedding of a triangulation, an edge flip is an operation that transforms the triangulation into a different one by replacing the diagonal of a quadrilateral formed by two adjacent triangles with the other possible diagonal. The flip graph is the graph with a vertex for each distinct triangulation and an edge between two vertices if their corresponding triangulations differ by a single flip. The flip graph is connected, and thus it makes sense to consider its diameter. In this talk we give an overview of the problem of finding upper and lower bounds on the diameter of the flip graph, and in particular we present the proof of the most recent upper bound of 5.2n - 30.8.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010