IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Superpatterns and Generalizations of Layered Permutations

  • Feb. 19, 2016
  • 2:30 p.m.
  • LeConte 312


For a set P of permutations, we say that a permutation is a P-superpattern if it contains every permutation in P as a pattern, and we denote by sp(P) the shortest length of all P-superpatterns. When P is the set of layered permutations of length k, it has been shown that sp(P) = Theta(k log(k)). The notion of superpatterns can be extended naturally to words. In this talk, we explore some generalizations of layered permutations to `layered words' and seek to find shortest lengths for superpatterns containing these sets.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster