Erdős--Szekeres-type problems in the real projective plane

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10453254" target="_blank" >RIV/00216208:11320/22:10453254 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.SoCG.2022.10" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2022.10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2022.10" target="_blank" >10.4230/LIPIcs.SoCG.2022.10</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Erdős--Szekeres-type problems in the real projective plane

Popis výsledku v původním jazyce

We consider point sets in the real projective plane $RPP$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on ErdH{o}s--Szekeres-type problems.We provide asymptotically tight bounds for a variant of the ErdH{o}s--Szekeres theorem about point sets in convex position in $RPP$, which was initiated by Harborth and M&quot;oller in 1994. The notion of convex position in $RPP$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k geq 3$, an (affine) $k$-hole in a finite set $S subseteq mathbb{R}^2$ is a set of $k$ points from $S$ in convex position with no point of $S$ in the interior of their convex hull. After introducing a new notion of $k$-holes for points sets from $RPP$, called projective $k$-holes, we find arbitrarily large finite sets of points from $RPP$ with no projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many projective $k$-holes for $k leq 7$. On the other hand,we show that the number of $k$-holes can be substantially larger in~$RPP$ than in $mathbb{R}^2$ by constructing,for every $k in {3,dots,6}$, sets of $n$ points from $mathbb{R}^2 subset RPP$ with $Omega(n^{3-3/5k})$ projective $k$-holes and only $O(n^2)$ affine $k$-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $RPP$ and about some algorithmic aspects.The study of extremal problems about point sets in $RPP$ opens a new area of research, which we support by posing several open problems.

Název v anglickém jazyce

Erdős--Szekeres-type problems in the real projective plane

Popis výsledku anglicky

We consider point sets in the real projective plane $RPP$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on ErdH{o}s--Szekeres-type problems.We provide asymptotically tight bounds for a variant of the ErdH{o}s--Szekeres theorem about point sets in convex position in $RPP$, which was initiated by Harborth and M&quot;oller in 1994. The notion of convex position in $RPP$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k geq 3$, an (affine) $k$-hole in a finite set $S subseteq mathbb{R}^2$ is a set of $k$ points from $S$ in convex position with no point of $S$ in the interior of their convex hull. After introducing a new notion of $k$-holes for points sets from $RPP$, called projective $k$-holes, we find arbitrarily large finite sets of points from $RPP$ with no projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many projective $k$-holes for $k leq 7$. On the other hand,we show that the number of $k$-holes can be substantially larger in~$RPP$ than in $mathbb{R}^2$ by constructing,for every $k in {3,dots,6}$, sets of $n$ points from $mathbb{R}^2 subset RPP$ with $Omega(n^{3-3/5k})$ projective $k$-holes and only $O(n^2)$ affine $k$-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $RPP$ and about some algorithmic aspects.The study of extremal problems about point sets in $RPP$ opens a new area of research, which we support by posing several open problems.

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/GA21-32817S" target="_blank" >GA21-32817S: Algoritmické, strukturální a složitostní aspekty geometrických konfigurací</a><br>

Návaznosti

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

Rok uplatnění

2022

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

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-227-3

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

15

Strana od-do

—

Název nakladatele

Schloss Dagstuhl

Místo vydání

Německo

Místo konání akce

Berlín

Datum konání akce

7. 6. 2022

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

WRD - Celosvětová akce

Kód UT WoS článku

—