Two extensions of the Erdős-Szekeres problem

DOI10.4171/JEMS/1000zbMATH Open1454.52015OpenAlexW3056765334MaRDI QIDQ2216751FDOQ2216751

Authors: Andreas Holmsen, János Pach, Gábor Tardos, Hossein Nassajian Mojarrad 

Publication date: 17 December 2020

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: According to Suk's breakthrough result on the Erdos-Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+Oleft(n^{2/3}lognight)}$ points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term. A family of $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Toth and by Pach and Toth, respectively. Let $c(n)$ (and $c^{\prime }(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)le{c}^{\prime }(n)leq{2}^{n+Oleft(sqrtnlognight)}$.

Full work available at URL: https://arxiv.org/abs/1710.11415

Recommendations

• The Erdős-Szekeres problem for non-crossing convex sets
• A generalisation of the Erdős-Szekeres theorem to disjoint convex sets
• On the Erdős-Szekeres convex polygon problem
• Erdős-Szekeres theorems for families of convex sets
• An improved upper bound for the Erdős-Szekeres conjecture

zbMATH Keywords

arrangements of pseudolinesErdős-Szekeres conjecture

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A generalisation of the Erdős-Szekeres theorem to disjoint convex sets
• A generalization of the Erdös-Szekeres convex n-gon theorem.
• A positive fraction Erdős-Szekeres theorem
• Axioms and hulls
• Canonical theorems for convex sets
• Convexity in topological affine planes
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Erdős-Szekeres-type theorems for segments and noncrossing convex sets
• Nine convex sets determine a pentagon with convex sets as vertices
• Order types of convex bodies
• Oriented Matroids
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• The Erdős-Szekeres problem for non-crossing convex sets
• The partitioned version of the Erdős-Szekeres theorem

Cited In (9)

• Regular systems of paths and families of convex sets in convex position
• An extension of the rainbow Erdős-Rothschild problem
• A SAT attack on higher dimensional Erdős-Szekeres numbers
• Coloring intersection hypergraphs of pseudo-disks
• The Dirac-Goodman-Pollack conjecture
• A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem
• Erdős-Szekeres-type problems in the real projective plane
• On the Erdős-Tuza-Valtr conjecture
• Erdős-Szekeres ``happy end-type theorems for separoïds

This page was built for publication: Two extensions of the Erdős-Szekeres problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216751)