vix.ing · top · new · best · stats · spec

On the Erdős-Szekeres convex polygon problem

2016/09/15 by Andrew Suk · 2 citations
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Digital Image Processing Techniques

paper · pdf · doi:10.1090/jams/869

openalex publication_date 2016/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper E upper S left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>E</mml:mi> <mml:mi>S</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">ES(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the smallest integer such that any set of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper E upper S left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>E</mml:mi> <mml:mi>S</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">ES(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> points in the plane in general position contains <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper E upper S left-parenthesis n right-parenthesis less-than-or-equal-to StartBinomialOrMatrix 2 n minus 4 Choose n minus 2 EndBinomialOrMatrix plus 1 equals 4 Superscript n minus o left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>E</mml:mi> <mml:mi>S</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-OPEN"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> </mml:mstyle> <mml:mfrac linethickness="0"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mn>4</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:mfrac> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-CLOSE"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:mstyle> </mml:mrow> </mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>4</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">ES(n) ≤ 2n - 4\choose n-2 + 1 = 4n -o(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In 1960, they showed that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper E upper S left-parenthesis n right-parenthesis greater-than-or-equal-to 2 Superscript n minus 2 Baseline plus 1"> <mml:semantics> <mml:mrow> <mml:mi>E</mml:mi> <mml:mi>S</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≥ </mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">ES(n) ≥ 2n-2 + 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and conjectured this to be optimal. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper E upper S left-parenthesis n right-parenthesis equals 2 Superscript n plus o left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>E</mml:mi> <mml:mi>S</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">ES(n) =2n +o(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .

Citations

Cited by

Related