Predicates whose maximal length functions increase periodically (Q919037): Difference between revisions

Let P be a predicate defined on finite sets of positive integers and define \(L_ p(n)\) to be the largest cardinality of subsets of \(\{\) 1,2,...,n\(\}\) for which P is false. In this paper the authors exhibit conditions on P which force the existence of integers N, M, and K so that \(L_ p(n+M)=L_ p(n)+K\) whenever \(n>N\) (for such predicates we say that \(L_ p\) increases periodically). In particular, the authors show that if D is a finite set of tuples of positive integers, then \(L_ p\) increases periodically for the predicate P \(=\) ``X contains an s-tuple \(\{a_ i\}^ s_ 1\) with \(\{a_{i+1}- a_ i\}_ 1^{s-1}\) in D''.