Flip distances between graph orientations
Jean Cardinal (ULB, Brussels)
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
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 |