2014/09/15 by Joshua Cooper, Cooper, Joshua, Anna Kirkpatrick +1
Computer Science · Mathematics · #06A07 (Primary) 05A05 #68Q17 (Secondary) #Advanced Combinatorial Mathematics #Bounded function #Combinatorics #Combinatorics (math.CO) #Dimension (graph theory) #Discrete mathematics #FOS: Mathematics #Injective function #Limits and Structures in Graph Theory #Mathematics #Partially ordered set #Permutation (music) #Physics #Polynomial #Time complexity #math.CO #msc:05A05 #msc:06A07 #msc:68Q17 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1409.4368
15 pages
arxiv created 2014/09/15 · openalex publication_date 2014/09/15 · arxiv updated 2014/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 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, and (2) is it #P-hard to count the number of texts which avoid a given pattern?