Rainbow cycles in flip graphs

DOI10.1137/18M1216456MaRDI QIDQ5208641zbMATHWikidataFDO

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)

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

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)

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$.

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

Cites work

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

Cited in

(8)

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

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)