IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The Complexity of Counting Poset and Permutation Patterns

  • Sept. 5, 2014
  • 2:30 p.m.
  • LeConte 312

Abstract

We introduce a notion of pattern occurrence that generalizes both classical permutation patterns as well as poset containment. Many questions about pattern statistics and avoidance generalize naturally to this setting, and we focus on functional complexity problems -- particularly those that arise by constraining the order dimensions of the pattern and text posets. We show that counting the number of induced, injective occurrences among dimension 2 posets is #P-hard; enumerating the linear extensions that occur in realizers of dimension 2 posets can be done in polynomial time, while for unconstrained dimension it is GI-complete; counting not necessarily induced, injective occurrences among dimension 2 posets is #P-hard; counting injective or not necessarily injective occurrences of an arbitrary pattern in a dimension 1 text is #P-hard, although it is in FP if the pattern poset is constrained to have bounded intrinsic width; and counting injective or not necessarily injective occurrences of a dimension 1 pattern in an arbitrary text is #P-hard, while it is in FP for bounded dimension texts. This framework easily leads to a number of open questions, chief among which are (1) is it #P-hard to count the number of occurrences of a dimension 2 pattern in a dimension 1 text, (2) is it #P-hard to count the number of texts which avoid a given dimension 2 pattern, and (3) what is the distribution of the number of order-automorphisms of a random permutation?

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