2000/06/26 by Walter D. Morris, Valeriu Soltan · 7 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.1090/s0273-0979-00-00877-6
openalex publication_date 2000/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
In 1935 Erdős and Szekeres proved that for any integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than-or-equal-to 3"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n ≥ 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> there exists a smallest positive integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</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">N(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that any set of at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</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">N(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> points in general position in the plane 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 that are the vertices of a convex <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> -gon. They also posed the problem to determine the value of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</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">N(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and conjectured that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N left-parenthesis n right-parenthesis equals 2 Superscript n minus 2 Baseline plus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</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">N(n) = 2n-2 +1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than-or-equal-to 3 period"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mn>3.</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n ≥ 3.</mml:annotation> </mml:semantics> </mml:math> </inline-formula> Despite the efforts of many mathematicians, the Erdős-Szekeres problem is still far from being solved. This paper surveys the known results and questions related to the Erdős-Szekeres problem in the plane and higher dimensions, as well as its generalizations for the cases of families of convex bodies and the abstract convexity setting.