{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:37:55Z","timestamp":1787326675798,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["413902284"],"award-info":[{"award-number":["413902284"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["GA 19-08554S"],"award-info":[{"award-number":["GA 19-08554S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>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 noncrossing perfect matchings on a set of $n$ points in convex position. In addition, we consider two flip graphs on classes of nongeometric 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 nonexistence of rainbow cycles for different values of $r$, $n$, and $k$.<\/jats:p>","DOI":"10.1137\/18m1216456","type":"journal-article","created":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T15:14:41Z","timestamp":1577978081000},"page":"1-39","source":"Crossref","is-referenced-by-count":6,"title":["Rainbow Cycles in Flip Graphs"],"prefix":"10.1137","volume":"34","author":[{"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leon","family":"Sering","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,1,2]]},"reference":[{"key":"atypb1","unstructured":"A. \u00c1d\u00e1m,\n                      Truth Functions and the Problem of Their Realization by Two-Terminal Graphs\n                      , Akad\u00e9miai Kiad\u00f3, Budapest, 1968."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0750-z"},{"key":"atypb3","unstructured":"N. Alon, A. Pokrovskiy, and B. Sudakov,\n                      Random Subgraphs of Properly Edge-Coloured Complete Graphs and Long Rainbow Cycles\n                      , preprint,https:\/\/arxiv.org\/abs\/1608.07028, 2016."},{"key":"atypb4","first-page":"7","volume":"52","author":"Alspach B.","year":"2008","journal-title":"Bull. Inst. Combin. Appl."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-12245"},{"key":"atypb6","unstructured":"J. Balogh and T. Molla,\n                      Long Rainbow Cycles and Hamiltonian Cycles Using Many Colors in Properly Edge-Colored Complete Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/1706.04950, 2017."},{"key":"atypb7","unstructured":"L. A. Berry, B. Reed, A. Scott, and D. R. Wood,\n                      A Logarithmic Bound for the Chromatic Number of the Associahedron\n                      , preprint,https:\/\/arxiv.org\/abs\/1811.08972, 2018."},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.37236\/1249","volume":"3","author":"Bhat G. S.","year":"1996","journal-title":"Electron. J. Combin."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.04.001"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90179-1"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114582"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322413"},{"key":"atypb13","first-page":"3","volume":"1","author":"Eppstein D.","year":"2010","journal-title":"J. Comput. Geom."},{"key":"atypb14","first-page":"47","volume":"11","author":"Fabila-Monroy R.","year":"2009","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"P. Gregor, T. M\u00fctze, and J. Nummenpalo,\n                      A short proof of the middle levels theorem\n                      , Discrete Anal., 2018.","DOI":"10.19086\/da.3659"},{"key":"atypb16","first-page":"570","volume":"2","author":"Hanke S.","year":"1996","journal-title":"J. Univers. Comput. Sci."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"E. Hartung, H. P. Hoang, T. M\u00fctze, and A. Williams,\n                      Combinatorial Generation via Permutation Languages. I. Fundamentals\n                      , to appear at the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020),https:\/\/arxiv.org\/abs\/1906.06069.","DOI":"10.1137\/1.9781611975994.74"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200038"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.018"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00016-4"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009464"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1963-0159764-2"},{"key":"atypb23","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming. Vol. $4$A. Combinatorial Algorithms. Part 1\n                      , Addison-Wesley, Upper Saddle River, NJ, 2011."},{"key":"atypb24","first-page":"17","volume":"3","author":"Kompel'makher V. L.","year":"1975","journal-title":"Kibernetica"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(89)80072-1"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. Li and L. Zhang,\n                      Better approximation of diagonal-flip transformation and rotation transformation\n                      , in Proceedings of the 4th Annual International Conference on Computing and Combinatorics, COCOON '98, Taipei, Taiwan, R.o.C., 1998, pp. 85-94,https:\/\/doi.org\/10.1007\/3-540-68535-9_12.","DOI":"10.1007\/3-540-68535-9_12"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90048-4"},{"key":"atypb28","first-page":"2014","volume":"73","author":"Manneville T.","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdw004"},{"key":"atypb30","unstructured":"A. Nijenhuis and H. S. Wilf,\n                      Combinatorial Algorithms: For Computers and Calculators, Computer Science and Applied Mathematics\n                      , 2nd ed., Academic Press, New York, 1978."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9922-7"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-018-0393-1"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.02.035"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22443"},{"key":"atypb35","first-page":"77","author":"Rogers R. O.","year":"1999","journal-title":"Boca Raton, FL"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90036-3"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0406012"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1988-0928904-4"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"H. F. Trotter,\n                      Algorithm 115: Perm\n                      , Commun. ACM, 5 (1962), pp. 434-435http:\/\/doi.acm.org\/10.1145\/368637.368660.","DOI":"10.1145\/368637.368660"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"H. S. Wilf,\n                      Combinatorial Algorithms: An Update\n                      , CBMS-NSF Regional Conf. Ser. in Appl. Math. 55, SIAM, Philadelphia, 1989,https:\/\/doi.org\/10.1137\/1.9781611970166.","DOI":"10.1137\/1.9781611970166"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1216456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:37Z","timestamp":1787322877000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1216456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1216456"],"URL":"https:\/\/doi.org\/10.1137\/18m1216456","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}