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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA21-32817S" target="_blank" >GA21-32817S: Algorithmic, structural and complexity aspects of geometric configurations</a><br>

Continuities

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

Publication year

2022

Confidentiality

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

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-227-3

ISSN

1868-8969

e-ISSN

—

Number of pages

15

Pages from-to

—

Publisher name

Schloss Dagstuhl

Place of publication

Německo

Event location

Berlín

Event date

Jun 7, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—