Permutations Avoiding Bipartite Partially Ordered Patterns Have a Regular Insertion Encoding Article Swipe

View

Related Concepts

Permutation (music) Combinatorics Encoding (memory) Mathematics Bipartite graph Class (philosophy) Generating function Function (biology) Discrete mathematics Computer science Genetics Biology Physics Graph Artificial intelligence Acoustics

Christian Bean , Émile Nadeau , Jay Pantone , Henning Úlfarsson ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.37236/12686 · OA: W4400589118

We prove that any class of permutations defined by avoiding a partially ordered pattern (POP) with height at most two has a regular insertion encoding and thus has a rational generating function. Then, we use Combinatorial Exploration to find combinatorial specifications and generating functions for hundreds of other permutation classes defined by avoiding a size 5 POP, allowing us to resolve several conjectures of Gao and Kitaev (2019) and of Chen and Lin (2024).