Article ID Journal Published Year Pages File Type
4656740 Journal of Combinatorial Theory, Series B 2015 32 Pages PDF
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/log⁡kn⩽k2+ck3/2/log⁡k, where c is some absolute positive constant.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,