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%2F24%3A10490825" target="_blank" >RIV/00216208:11320/24:10490825 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=FiPP~2wWg6" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=FiPP~2wWg6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-024-00691-5" target="_blank" >10.1007/s00454-024-00691-5</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 RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erd &amp; odblac;s-Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erd &amp; odblac;s-Szekeres theorem about point sets in convex position in RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document}, which was initiated by Harborth and M &amp; ouml;ller in 1994. The notion of convex position in RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} agrees with the definition of convex sets introduced by Steinitz in 1913. For k &gt;= 3documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$k ge 3$$end{document}, an (affine) k-hole in a finite set S subset of R2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$S subseteq {mathbb {R}}&lt;^&gt;2$$end{document} 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 RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document}, called projective k-holes, we find arbitrarily large finite sets of points from RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} 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 &lt;= 7documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$k le 7$$end{document}. On the other hand, we show that the number of k-holes can be substantially larger in RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} than in R2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${mathbb {R}}&lt;^&gt;2$$end{document} by constructing, for every k is an element of{3,&amp; ctdot;,6}documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$k in {3,dots ,6}$$end{document}, sets of n points from R2 subset of RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${mathbb {R}}&lt;^&gt;2 subset {{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} with Omega(n3-3/5k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$Omega (n&lt;^&gt;{3-3/5k})$$end{document} projective k-holes and only O(n2)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$O(n&lt;^&gt;2)$$end{document} affine k-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} and about some algorithmic aspects. The study of extremal problems about point sets in RP2documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$${{,mathrm{{mathbb {R}}{mathcal {P}}&lt;^&gt;2},}}$$end{document} opens a new area of research, which we support by posing several open problems.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

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

2024

Confidentiality

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

Name of the periodical

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

1432-0444

Volume of the periodical

72

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

34

Pages from-to

1545-1578

UT code for WoS article

001308255600001

EID of the result in the Scopus database

2-s2.0-85203307226