Charles Explorer logo
🇨🇿

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

Publikace na Matematicko-fyzikální fakulta |
2022

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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 Erd\H{o}s--Szekeres-type problems.

We provide asymptotically tight bounds for a variant of the Erd\H{o}s--Szekeres theorem about point sets in convex position in $\RPP$, which was initiated by Harborth and M\"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.