Permutations Avoiding Arithmetic Progressions

Phani Raj Lolakapuri
Kshitij Gajjar
Friday, 11 Nov 2016, 16:00 to 17:30
A-201 (STCS Seminar Room)
In 1977, J.A. Davis et al showed that any finite subset of natural numbers can be permuted such that it does not contain any 3-term A.P. as a sub-sequence. However, this is not true for the set of all natural numbers. Furthermore, they also show that there exists a permutation of natural numbers which does not contain any 5-term A.P. as a sub-sequence.
Generalizing this, we say that a subset of natural numbers is k-avoidable if there exists a permutation of the elements of the set which does not contain any k-term A.P. as a sub-sequence. In 2008, LeSaulnier and S. Vijay gave bounds on the densities of subsets of natural numbers which are 3-avoidable and 4-avoidable. In this talk, I will discuss my contribution (in collaboration with S. Vijay) to this work, which was an improvement over these bounds.