Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656740 | Journal of Combinatorial Theory, Series B | 2015 | 32 Pages |
Abstract
One of the most classical results in Ramsey theory is the theorem of Erdős and Szekeres from 1935, which says that every sequence of more than k2k2 numbers contains a monotone subsequence of length k+1k+1. We address the following natural question motivated by this result: Given integers k and n with n⩾k2+1n⩾k2+1, how many monotone subsequences of length k+1k+1 must every sequence of n numbers contain? We answer this question precisely for all sufficiently large k and n⩽k2+ck3/2/logkn⩽k2+ck3/2/logk, where c is some absolute positive constant.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wojciech Samotij, Benny Sudakov,