# On the Erdos-Szekeres convex polygon problem

@article{Suk2016OnTE, title={On the Erdos-Szekeres convex polygon problem}, author={Andrew Suk}, journal={ArXiv}, year={2016}, volume={abs/1604.08657} }

Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdos-Szekeres conjecture by showing that $ES(n) =2^{n +o(n)}$.

#### 40 Citations

Erdös-Szekeres Convex Polygon Problem

- 2017

A set of points in the plane is said to be in general position if it contains no three points on a line. A finite set of points in the plane is in convex position, if it is the vertex set of a convex… Expand

On some algebraic and extremal problems in discrete geometry

- Mathematics
- 2017

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer $n\ge 3$, we… Expand

Point Sets with Small Integer Coordinates and No Large Convex Polygons

- Computer Science, Mathematics
- Discret. Comput. Geom.
- 2018

This paper shows how to realize Erdős and Szekeres' proofs of convex polygon construction in an integer grid of size O(n^2 \log _2(n)^3). Expand

Two extensions of the Erd\H{o}s-Szekeres problem

- Mathematics
- 2017

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

THE ERDŐS–SZEKERES PROBLEM AND AN INDUCED RAMSEY QUESTION

- Mathematics
- Mathematika
- 2019

Motivated by the Erdos-Szekeres convex polytope conjecture in $R^d$, we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers $ n > k \geq 5$, what is the minimum… Expand

On Erdős-Szekeres-Type Problems for k-convex Point Sets

- Mathematics, Computer Science
- IWOCA
- 2019

The well-known Erdős–Szekeres Theorem is extended by showing that, for every fixed \(k \in \mathbb {N}\), every set of n points in the plane in general position contains a k-convex subset of size at least \(\varOmega (\log ^k{n})\). Expand

Two extensions of the Erdős–Szekeres problem

- Mathematics
- 2017

According to Suk’s breakthrough result on the Erdős–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… Expand

On Equal Point Separation by Planar Cell Decompositions

- Mathematics
- 2017

In this paper, we investigate the problem of separating a set $X$ of points in $\mathbb{R}^{2}$ with an arrangement of $K$ lines such that each cell contains an asymptotically equal number of points… Expand

On weighted sums of numbers of convex polygons in point sets

- Mathematics
- 2019

Let $S$ be a set of $n$ points in general position in the plane, and let $X_{k,\ell}(S)$ be the number of convex $k$-gons with vertices in $S$ that have exactly $\ell$ points of $S$ in their… Expand

On Erdős-Szekeres-type problems for k-convex point sets

- Computer Science, Mathematics
- Eur. J. Comb.
- 2020

The well-known Erdős–Szekeres Theorem is extended by showing that, for every fixed k ∈ N, every set of n points in the plane in general position contains a k -convex subset of size at least Ω ( log k n ) . Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

The Erdos-Szekeres problem on points in convex position – a survey

- Mathematics
- 2000

In 1935 Erdős and Szekeres proved that for any integer n ≥ 3 there exists a smallest positive integer N(n) such that any set of at least N(n) points in general position in the plane contains n points… Expand

An Improved Upper Bound for the Erdős–Szekeres Conjecture

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2016

This paper proves that 2n-2+1 is the minimum natural number such that every set of ES(n) points in general position in the plane contains n points in convex position. Expand

Note on the Erdos - Szekeres Theorem

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1998

The upper bound to the least integer such that among any g(n) points in general position in the plane there are always n in convex position is improved. Expand

Erdős–Szekeres Without Induction

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2016

The current best upper bound for estimating ES(n) is 2932, due to Vlachos (On a conjecture of Erdős and Szekeres, 2015). Expand

Finding Convex Sets Among Points in the Plane

- Computer Science, Mathematics
- Discret. Comput. Geom.
- 1998

It is shown that g(n) is the least value such that any points in the plane in general position contain the vertices of a convex n -gon, the first improvement since the original Erdős—Szekeres paper. Expand

Ramsey-remainder for convex sets and the Erdös-Szekeres theorem

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2001

The exact conditions under which, for sufficiently large n, any set of 4n points, in general position in the plane, can be partitioned into n convex quadrilaterals are found. Expand

Forced Convex n -Gons in the Plane

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1998

The +1 is removed from the upper bound for n ≥ 4 and the bounds which have stood unchanged since 1935 areremoved. Expand

Erdos-Szekeres-type theorems for monotone paths and convex bodies

- Mathematics
- 2012

For any sequence of positive integers j(1) = 2 and q >= 2, what is the smallest integer N with the property that no matter how we color all k-element subsets of [N]={1, 2, ..., N} with q colors, we… Expand

The Erdős – Szekeres Theorem : Upper Bounds and Related Results

- 2004

Let ES(n) denote the least integer such that among any ES(n) points in general position in the plane there are always n in convex position. In 1935, P. Erdős and G. Szekeres showed that ES(n) exists… Expand

On some extremum problems in elementary geometry

- Mathematics
- 2006

1. Let S denote a set of points in the plane, N(S) the number of points in S. More than 25 years ago we have proved [2] the following conjecture of ESTHER KLEINSZERERES: There exists a positive… Expand