For two permutations sigma and pi, we say that sigma contains a copy of pi, if there is a subset (not necessarily consecutive) of elements in sigma, whose relative order is the same as in pi. For example, if pi = (1,2,3), then a copy of pi in sigma amounts to an increasing subsequence in sigma of length 3.

As shown by Guillemot and Marx, a copy of a constant length pi can be found in sigma in linear time. However, how quickly can one find such a pattern if guaranteed that sigma contains *many* disjoint copies of pi ? It was shown by Newman, Rabinovich, Rajendraprasad and Sohler that the answer to this question is heavily dependent on the structure of the pattern and the amount of adaptivity of the algorithm. In this talk, I will focus on non-adaptive algorithms, proving some tight upper and lower bounds and demonstrating several surprising phenomena.

Based on joint work with Clement Canonne.