Rainbow cycles in flip graphs

DOI10.1137/18M1216456zbMATH Open1430.52009arXiv1712.07421WikidataQ126413675 ScholiaQ126413675MaRDI QIDQ5208641FDOQ5208641

Authors: Stefan Felsner, Linda Kleist, Torsten Mütze, Leon Sering 

Publication date: 9 January 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon, and an edge between any two triangulations that differ in exactly one edge. An $r$-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly $r$ times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of $r$-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex $n$-gon, the flip graph of plane trees on an arbitrary set of $n$ points, and the flip graph of non-crossing perfect matchings on a set of $n$ points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of $1,2,dots,n$ and the flip graph of $k$-element subsets of $1,2,dots,n$. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of $r$, $n$ and~$k$.

Full work available at URL: https://arxiv.org/abs/1712.07421

Recommendations

• Rainbow cycles in flip graphs
• On the chromatic number of some flip graphs
• On flips in planar matchings
• Triangle-free triangulations
• Graph of triangulations of a convex polygon and tree of triangulations

zbMATH Keywords

permutationmatchingtriangulationGray coderainbow cyclespanning treeflip graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) General convexity (52A99)

Cites Work

• Title not available (Why is that?)
• Flipping edges in triangulations
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Title not available (Why is that?)
• Some Hamilton Paths and a Minimal Change Algorithm
• The rotation graph of binary trees is Hamiltonian
• A Survey of Combinatorial Gray Codes
• Generation of Permutations by Adjacent Transposition
• The associahedron and triangulations of the \(n\)-gon
• Gray codes for non-crossing partitions and dissections of a convex polygon
• Flips in planar graphs
• Balanced Gray codes
• Title not available (Why is that?)
• The wonderful Walecki construction
• On the chromatic number of some flip graphs
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Title not available (Why is that?)
• Gray codes with restricted density
• Graphs of non-crossing perfect matchings
• Adjacent interchange generation of combinations
• The diameter of associahedra
• Graph properties of graph associahedra
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Graph of triangulations of a convex polygon and tree of triangulations
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• Gray code enumeration of plane straight-line graphs
• Happy endings for flip graphs
• Proof of the middle levels conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The genus of curve, pants and flip graphs
• Once punctured disks, non-convex polygons, and pointihedra
• A short proof of the middle levels theorem
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Eccentricities in the flip‐graphs of convex polygons
• Edge Conflicts do not Determine Geodesics in the Associahedron

Cited In (7)

• Triangle-free triangulations
• Rainbow Cycles in Flip Graphs.
• On the chromatic number of some flip graphs
• On flips in planar matchings
• Triangle-free triangulations, hyperplane arrangements and shifted tableaux
• Flipping triangles and rectangles
• Rainbow Odd Cycles

This page was built for publication: Rainbow cycles in flip graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5208641)