A combinatorial problem in geometry

By P. Erdös, G. Szekeres. 2009

1,307 citations recorded by the source corpus.

Subfields: Geometry and Topology, Mathematical Physics, Theoretical Computer Science

View Paper: https://www.semanticscholar.org/paper/cc87a0d285799418f19a0daf11571e26915b9114

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Theoretical Computer Science

Citations in the corpus

On the independence number of the Erdos-Rényi and projective norm graphs and a related hypergraph (2007, methodology): “To finish the proof, we apply the classical bound of Erdős and Szekeres [4] (see also [5]) for the usual graph Ramsey numbers.”
Regularity lemma for distal structures (2015, background): “A classical theorem of Erdős-Szekeres [15] states that every graph on n vertices contains a homogeneous subset of size at least 1 2 logn (all log’s are of base two), and this bound is tight up to a constant multiple.”
An exponential improvement for diagonal Ramsey (2023, background): “Erdős and Szekeres [11] proved that R(k, `) 6 ( k + ` ` ) (1) for all k, ` ∈ N, and this bound was improved by Thomason [21], Conlon [5] and Sah [18] when ` = Θ(k), the best known bound in this case1 being of the form R(k, `) 6 e−c(log k) 2 ( k + ` ` ) for some c > 0.”
Ramsey numbers of degenerate graphs (2015, background): “In 1935, Erd˝os and Szekeres [14] rediscovered Ramsey’s theorem and brought it to more widespread attention by ﬁnding interesting geometric applications of its hypergraph extensions.”
Unsolved Problems in Combinatorial Games (2009, neutral): “[26] (and see Schen-sted [103]) was introduced by Harary et al. [52].”
Permutation classes (2014, background): “Roughly twenty-five years after Erdős and Szekeres, Schensted’s famous paper [146] on increasing and decreasing subsequences was published.”
The triangle-free process and R(3,k) (2013, background): “hin a factor of 4+ o(1) of the best known upper bound, proved by Shearer over 25 years ago. 1. Introduction For more than eighty years, since the seminal papers of Ramsey [44] and Erd}os and Szekeres [32], the area now known as Ramsey Theory has been of central importance in Combinatorics. The subje”
Geometric Range Searching and Its Relatives (2007, methodology): “Matou sek and Welzl [186] gave an entirely di erent algorithm for the halfspace rangecounting problem in the plane, using a combinatorial result of Erd} os and Szekeres [112].”
Hypergraph Ramsey numbers (2008, methodology): “Finally, we make some progress on related hypergraph Ramsey-type problems.”
Ramsey Theory, integer partitions and a new proof of the Erdős–Szekeres Theorem (2012, methodology): “We say that H contains a monotone path of length n if there are x1 x2 · · · xn+k−1 so that H contains all n edges of the form {xi, xi+1, . . . , xi+k−1}.”
The asymptotics of r(4,t) (2023, background): “Since the original bounds of Erdős and Szekeres [15] in 1935, estimates for r(s, t) have been the subject of extensive research; for instance the conjecture r(s, t) = Θ∗(ts−1) as t→∞ dates back to at least 1947 – see Erdős [14] and Chung and Graham [10] – here the star denotes implicit polylogarithm”
Erdős-Hajnal-type Results on Intersection Patterns of Geometric Objects (2008, background): “According to the results of Erdős [20] and Erdős and Szekeres [23] quoted in the introduction, there are n-vertex graphs that are 2 log n-Ramsey, but no n-vertex graph is 1 2 log n-Ramsey.”
Graph structure via local occupancy (2020, background): “By the Ramsey number upper bound of Erdős and Szekeres [29], in any S ⊆ V (G) such that |S| ≥ n/(logn)2, there is guaranteed to be an independent set of G of size q, for some q satisfying q = (12 + o(1)) log2 n as n→∞.”
Spectral graph theory (2019, background): “For the upper bounds, Erdős and Szekeres [12] (1935) show, by a nice inductive proof, that r(s, t) ≤ ( s+t−2 s−1 ) .”
Erdős–Szekeres‐type theorems for monotone paths and convex bodies (2011, background): “Bisztriczky and Fejes Tóth [5] generalized the Happy Ending theorem of Erdős and Szekeres [6, 16] as follows.”
Diagonal Ramsey via effective quasirandomness (2020, background): “The standard Erdő–Szekeres [9] proof goes as follows.”
Small permutation classes (2007, background): “s the permutation classes of growth rate 0: if C contains arbitrarily long monotone permutations then grpCq ě 1while otherwise C is ﬁnite and so grpCq exists and equals 0. The Erdo˝s-Szekeres Theorem [18]. Every permutation π of length pm ´ 1q2 ` 1contains a monotone permutation of length at least m”