Flip distances between graph orientations

Jean Cardinal (ULB, Brussels)

13-Oct-2020, 16:30-17:00 (3 years ago)

Abstract: Flip graphs encode relations induced on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider the structure and complexity of this problem for orientations of a graph in which every vertex has a specified outdegree, and a flip consists of reversing all edges of a directed cycle.

Joint work with Oswin Aichholzer, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber.

discrete mathematicscombinatorics

Audience: researchers in the topic

( paper | slides | video )


LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

Organizers: Igor Pak*, Greta Panova
*contact for this listing

Export talk to