Manfred Scheucher:


Erd\H{o}s--Szekeres-type problems in the real projective plane

Abstract: In this talk 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.

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 result by
Horton from 1983. Since 6-holes exist in sufficiently large point sets,
only the existence of projective $7$-holes remains open.

Similar as in the affine case, Horton sets only have quadratically many
projective $k$-holes for $k \leq 7$. However, in general the number of
$k$-holes can be substantially larger in $\RPP$ than in $\mathbb{R}^2$
and we construct 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 for every $k \in \{3,\dots,6\}$. Last but not least, we
discuss 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.

This is joint work with Martin Balko and Pavel Valtr.
To appear at SoCG 2022, see http://arxiv.org/abs/2203.07518