Csaba Tóth

Wednesday, May 16 at 11:15 AM

Abstract

Let S be a finite set of points in general position in the plane, and G(S) a family of planar straight-line graphs with vertex set S (such as noncrossing matching, spanning trees, spanning cycles, triangulations). Combinatorial properties of G(S) are often rely on operations (moves) that transform one graph in G(S) into another by replacing some edges; such as edge exchange, edge flip, edge rotation, and edge slide (either as elementary moves that modify a constant number of edges, or simultaneous operations that perform one or more elementary moves simultaneously). In a transition graph, the vertices represent the graphs in G(S), and adjacency represents a valid transformation. This talk will review recent results on the extremal properties of transition graphs and pose open problems.