Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00551784" target="_blank" >RIV/67985807:_____/21:00551784 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-030-92931-2_15" target="_blank" >http://dx.doi.org/10.1007/978-3-030-92931-2_15</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-92931-2_15" target="_blank" >10.1007/978-3-030-92931-2_15</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Popis výsledku v původním jazyce
Let V_n be a set of n points in the plane and let x∈V_n . An x-loop is a continuous closed curve not containing any point of V_n . We say that two x-loops are non-homotopic if they cannot be transformed continuously into each other without passing through a point of Vn . For n=2, we give an upper bound e^O(k^(1/2)) on the maximum size of a family of pairwise non-homotopic x-loops such that every loop has fewer than k self-intersections and any two loops have fewer than k intersections. The exponent O(k^(1/2)) is asymptotically tight. The previous upper bound 2^((2k)^4) was proved by Pach et al. [6]. We prove the above result by proving the asymptotic upper bound e^O(k^(1/2)) for a similar problem when x∈V_n, and by proving a close relation between the two problems.
Název v anglickém jazyce
Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Popis výsledku anglicky
Let V_n be a set of n points in the plane and let x∈V_n . An x-loop is a continuous closed curve not containing any point of V_n . We say that two x-loops are non-homotopic if they cannot be transformed continuously into each other without passing through a point of Vn . For n=2, we give an upper bound e^O(k^(1/2)) on the maximum size of a family of pairwise non-homotopic x-loops such that every loop has fewer than k self-intersections and any two loops have fewer than k intersections. The exponent O(k^(1/2)) is asymptotically tight. The previous upper bound 2^((2k)^4) was proved by Pach et al. [6]. We prove the above result by proving the asymptotic upper bound e^O(k^(1/2)) for a similar problem when x∈V_n, and by proving a close relation between the two problems.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GJ20-27757Y" target="_blank" >GJ20-27757Y: Náhodné diskrétní struktury</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2021
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Graph Drawing and Network Visualization. 29th International Symposium GD 2021, Revised Selected Papers
ISBN
978-3-030-92930-5
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
13
Strana od-do
210-222
Název nakladatele
Springer
Místo vydání
Cham
Místo konání akce
Tübingen
Datum konání akce
14. 9. 2021
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—