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

Výsledek na webu

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

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

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

Druh

J_imp - Článek v periodiku v databázi Web of Science

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í

2024

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 periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

1432-0444

Svazek periodika

72

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

34

Strana od-do

1545-1578

Kód UT WoS článku

001308255600001

EID výsledku v databázi Scopus

2-s2.0-85203307226