Permutation patterns are hard to count

DOI10.1137/1.9781611974331.CH66MaRDI QIDQ4575645zbMATH OpenOpenAlexFDO

Authors Igor Pak, Scott M. Garrabrant

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch66

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the number of permutations avoiding a given pattern
• Permutations avoiding sets of patterns with long monotone subsequences
• The number of permutations avoiding a set of generalized permutation patterns
• Finding and counting permutations via CSPs
• Finding and Counting Permutations via CSPs

Cited in

(7)

• Supercritical sequences, and the nonrationality of most principal permutation classes
• The complexity of counting poset and permutation patterns
• Interview with Igor Pak
• Words in linear groups, random walks, automata and P-recursiveness
• Combinatorial generation via permutation languages. I: Fundamentals
• The number of occurrences of patterns in a random tree or forest permutation
• Finitely generated subgroups of free groups as formal languages and their cogrowth

This page was built for publication: Permutation patterns are hard to count

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575645)