Ramsey Theory, integer partitions and a new proof of the Erd?s-Szekeres Theorem

摘要

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_i < X_2 < ??? < x_(n+k-1) so that H contains all n edges of the form {x_i, x_(i+i),. . ., x_(i+k-i)}. 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-0(1))n))) where the height of the tower is k — 2, thus resolving an open problem raised by Eliá? 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.