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


Zeichnung

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
    Erik Tadewaldt
  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
    Adam Schweitzer

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
  3. Sweeps, arrangements and signotopes
    Stefan Felsner and Helmut Weil
    Discrete Applied Mathematics 109 (2001) 67–94
  4. Happy Endings for Flip Graphs
    David Eppstein
    Journal of Computational Geometry 1(1)(2010) 3-28
  5. T-tetrominoes tiling’s Markov chain mixes fast
    K.K. Kayibi and S. Pirzada
    Theoretical Computer Science 714 (2018) 1–14
  6. 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
  7. Using contracted solution graphs for solving reconfiguration problems
    Paul Bonsma and Daniël Paulusma
    Acta Informatica 56 (2019) 619–648
  8. Enumerating degree sequences in digraphs and a cycle–cocycle reversing system
    Emeric Gioan
    European Journal of Combinatorics 28 (2007) 1351–1366
  9. Graph Properties of Graph Associahedra
    Thibault Manneville and Vincent Pilaud
    Séminaire Lotharingien de Combinatoire 73 (2015), Article B73d
  10. 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
  11. Multitriangulations as Complexes of Star Polygons
    Vincent Pilaud and Francisco Santos
    Discrete and Computational Geometry 41 (2009) 284–317
  12. Lattice Structures from Planar Graphs
    Stefan Felsner
    Electronic Journal of Combinatorics 11 (2004) R15
  13. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips) Uli Wagner and Emo Welzl
    Symposium on Computational Geometry (SoCG) 2020
  14. Efficient generation of elimination trees and graph associahedra
    Jean Cardinal, Arturo Merino, and Torsten Mütze
    Symposium on Discrete Algorithms (SODA) 2022
  15. Combinatorial generation via permutation languages
    Elizabeth Hartung, Hung P. Hoang, Torsten Mütze, and Aaron Williams
    Symposium on Discrete Algorithms (SODA) 2020
  16. Mixing of Permutations by Biased Transpositions
    Shahrzad Haddadan and Peter Winkler
    Theory of Computing Systems 63 (2019) 1068–1088
  17. Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees
    Igor Pak
    Discrete Mathematics 204 (1999) 329-335

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik
       Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.

Zuletzt bearbeitet März 2022