Flips and Flip-Graphs -- Sommersemester 2022
 Seminar Ausgewählte Kapitel der Graphentheorie: Flips and Flip-Graphs Sommersemester 2022 Prof. Stefan Felsner Sprechstunde n.V. LV-Nr.: 3236 L 316

## Aktuell:

Das Seminar findet vom 15. bis 17. Juli in der Jugendherberge Wandlitz statt.

Das Seminar wird von der Arbeitsgruppe unterstützt, insbesondere von
Helena Bergold, Manfred Scheucher, Felix Schröder und Sandro Roch.

## Thema:

A flip is a local change which maps a combinatorial structure into another. Flip-graphs have the structures as vertices and the flips as edges. The figure on this page shows the flip-graph of acyclic orientations of the 4-cycle - you may enjoy verifying this.

Flips and flip-graphs are omnipresent in discrete mathematics, for example they are implicitly used in gray-codes, reconfiguration problems, combinatorial markov chains and some enumeration algorithms. Some instances of flip-graphs, however, have receives a lot of attention in their own right. Here are three examples: (1) The flip-graph of adjacent transpositions of permutations is the skeleton graph of the permutahedron and the cover graph of the weak Bruhat order. (2) The flip-graph of rotations of binary trees is the skeleton graph of the associahedron and also the flip-graph of triangulations of points in convex position. (3) The flip-graphs of triangulations of other point sets still hold a lot of secrets.

In this seminar we want to look at selected papers to learn about the many colorful faces of flips and flip-graphs.

## Poster:

1. Connectivity of Triangulation Flip Graphs in the Plane
Malin Heinacher
2. Diagonal Flips in Hamiltonian Triangulations
Noyan Ugur
3. Happy endings for flip graphs (english version)
Xueyi Guo
4. T-tetrominoes Tiling's Markov chain mixes fast
Marcel Bösl
5. Using contracted solution graphs reconfiguration
Hans Schwarzkopf
6. Combinatorial generation via permutation languages
7. Efficient generation of elimination trees and graph associahedra
Julian Sampels
8. Multitriangulations as Complexes of Star Polygons
Maria Bulychev
9. Enumerating degree sequences in digraphs and cycle–cocycle
Eva Szilagyi
10. Sweeps, arrangements and signotopes
Robert Lauff
11. Lattice Structures from Planar Graphs

## References -- Quellen:

1. Connectivity of Triangulation Flip Graphs in the Plane
Uli Wagner and Emo Welzl
Symposium on Discrete Algorithms (SODA) 2020
1. Diagonal Flips in Hamiltonian Triangulations on the Sphere
Ryuichi Mori, Atsuhiro Nakamoto, and Katsuhiro Ota
Graphs and Combinatorics 19 (2003) 413–418
2. Making triangulations 4-connected using flips
Prosenjit Bose, Dana Jansens, André van Renssen, Maria Saumell, and Sander Verdonschot
Computational Geometry 47 (2014) 187–197
2. Sweeps, arrangements and signotopes
Stefan Felsner and Helmut Weil
Discrete Applied Mathematics 109 (2001) 67–94
3. Happy Endings for Flip Graphs
David Eppstein
Journal of Computational Geometry 1(1)(2010) 3-28
4. T-tetrominoes tiling’s Markov chain mixes fast
Theoretical Computer Science 714 (2018) 1–14
5. Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs
Stefan Felsner and Daniel Heldt
Discrete Mathematics and Theoretical Computer Science 18 (2016) #20
6. Using contracted solution graphs for solving reconfiguration problems
Paul Bonsma and Daniël Paulusma
Acta Informatica 56 (2019) 619–648
7. Enumerating degree sequences in digraphs and a cycle–cocycle reversing system
Emeric Gioan
European Journal of Combinatorics 28 (2007) 1351–1366
8. Graph Properties of Graph Associahedra
Thibault Manneville and Vincent Pilaud
Séminaire Lotharingien de Combinatoire 73 (2015), Article B73d
9. Flip Distances Between Graph Orientations
Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber
Algorithmica 83 (2021) 116–143
10. Multitriangulations as Complexes of Star Polygons
Vincent Pilaud and Francisco Santos
Discrete and Computational Geometry 41 (2009) 284–317
11. Lattice Structures from Planar Graphs
Stefan Felsner
Electronic Journal of Combinatorics 11 (2004) R15
12. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips) Uli Wagner and Emo Welzl
Symposium on Computational Geometry (SoCG) 2020
13. Efficient generation of elimination trees and graph associahedra
Jean Cardinal, Arturo Merino, and Torsten Mütze
Symposium on Discrete Algorithms (SODA) 2022
14. Combinatorial generation via permutation languages
Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, and Aaron Williams
Symposium on Discrete Algorithms (SODA) 2020
15. Mixing of Permutations by Biased Transpositions