Ramsey Theory, integer partitions and a new proof of the Erdős–Szekeres Theorem

By Guy Moshkovitz, Asaf Shapira. 2012

78 citations recorded by the source corpus.

Abstract Let H be a k -uniform hypergraph whose vertices are the integers 1 , … , N . We say that H contains a monotone path of length n if there are x 1 x 2 ⋯ x n + k − 1 so that H contains all n edges of the form { x i , x i + 1 , … , x i + k − 1 } . Let N k ( q , n ) be the smallest integer N so that every q -coloring of the edges of the complete k -uniform hypergraph on N vertices contains a monochromatic monotone path of length n . While the study of N k ( q , n ) for specific values of k and q goes back (implicitly) to the seminal 1935 paper of Erdős and Szekeres, the problem of bounding N k ( q , n ) for arbitrary k and q was studied by Fox, Pach, Sudakov and Suk. Our main contribution here is a novel approach for bounding the Ramsey-type numbers N k ( q , n ) , based on establishing a surprisingly tight connection between them and the enumerative problem of counting high-dimensional integer partitions. Some of the concrete results we obtain using this approach are the following: • We show that for every fixed q we have N 3 ( q , n ) = 2 Θ ( n q − 1 ) , thus resolving an open problem raised by Fox et al. • We show that for every k ≥ 3 , N k ( 2 , n ) = 2 ⋅ ⋅ 2 ( 2 − o ( 1 ) ) n where the height of the tower is k − 2 , thus resolving an open problem raised by Elias and Matousek. • We give a new pigeonhole proof of the Erdős–Szekeres Theorem on cups-vs-caps, similar to Seidenberg's proof of the Erdős–Szekeres Lemma on increasing/decreasing subsequences.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

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