On flips in planar matchings

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10423563" target="_blank" >RIV/00216208:11320/20:10423563 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-60440-0_17" target="_blank" >https://doi.org/10.1007/978-3-030-60440-0_17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-60440-0_17" target="_blank" >10.1007/978-3-030-60440-0_17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On flips in planar matchings

Popis výsledku v původním jazyce

In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Consider all non-crossing straight-line perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. The graph Hn has those matchings as vertices, and an edge between any two matchings that differ in replacing two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, provided that the quadrilateral contains the center of the unit circle. We show that the graph Hn is connected for odd n, but has exponentially many small connected components for even n, which we characterize and count via Catalan and generalized Narayana numbers. For odd n, we also prove that the diameter of Hn is linear in n. Furthermore, we determine the minimum and maximum degree of Hn for all n, and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles, and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, Mütze, and Sering.

Název v anglickém jazyce

On flips in planar matchings

Popis výsledku anglicky

In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Consider all non-crossing straight-line perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. The graph Hn has those matchings as vertices, and an edge between any two matchings that differ in replacing two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, provided that the quadrilateral contains the center of the unit circle. We show that the graph Hn is connected for odd n, but has exponentially many small connected components for even n, which we characterize and count via Catalan and generalized Narayana numbers. For odd n, we also prove that the diameter of Hn is linear in n. Furthermore, we determine the minimum and maximum degree of Hn for all n, and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles, and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, Mütze, and Sering.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-08554S" target="_blank" >GA19-08554S: Struktury a algoritmy ve velmi symetrických grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Lecture Notes in Computer Science

ISBN

978-3-030-60439-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

213-225

Název nakladatele

SPRINGER

Místo vydání

Neuveden

Místo konání akce

Leeds

Datum konání akce

24. 6. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—