Cyclic pattern containment and avoidance

DOI10.1016/J.AAM.2022.102320zbMATH Open1484.05006arXiv2106.02534OpenAlexW4205229072MaRDI QIDQ2078930FDOQ2078930

Alexander Sietsema, Rachel Domagalski, Quinn Minnich, Bruce E. Sagan, Sergi Elizalde, Jinting Liang, Jamie Schmidt

Publication date: 4 March 2022

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: The study of pattern containment and avoidance for linear permutations is a well-established area of enumerative combinatorics. A cyclic permutation is the set of all rotations of a linear permutation. Callan initiated the study of permutation avoidance in cyclic permutations and characterized the avoidance classes for all single permutations of length 4. We continue this work. In particular, we establish a cyclic variant of the Erdos-Szekeres Theorem that any linear permutation of length mn+1 must contain either the increasing pattern of length m+1 or the decreasing pattern of length n+1. We then derive results about avoidance of multiple patterns of length 4. We also determine generating functions for the cyclic descent statistic on these classes. Finally, we end with various open questions and avenues for future research.

Full work available at URL: https://arxiv.org/abs/2106.02534

zbMATH Keywords

pattern avoidance[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Szekeres+theorem&go=Go Erd��s-Szekeres theorem]cyclic permutationpattern containmentvincular patternconsecutive patterncyclic descent

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted permutations
• Pattern avoidance in ``flattened partitions
• Generating functions for generating trees
• Generalized permutation patterns and a classification of the Mahonian statistics
• Permutations with given peak set
• Permutations and words counted by consecutive patterns
• Generating trees and the Catalan and Schröder numbers
• Cyclic permutations realized by signed shifts
• Consecutive patterns in permutations
• Permutation patterns and statistics
• Enriched 𝑃-Partitions
• Peak sets of classical Coxeter groups
• The number of Baxter permutations
• Shuffle algebras, homology, and consecutive pattern avoidance
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Generating trees and forbidden subsequences
• Patterns in colored circular permutations
• Permutations with forbidden subsequences and a generalized Schröder number
• Multi-avoidance of generalised patterns
• Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
• Vincular pattern avoidance on cyclic permutations
• On rotated Schur-positive sets
• A survey of consecutive patterns in permutations
• Pattern avoidance in permutations: Linear and cyclic orders
• Schur-positive sets of permutations via products and grid classes
• Pattern avoidance of \([4,k]\)-pairs in circular permutations
• Generating functions for permutations avoiding a consecutive pattern
• A proof of the peak polynomial positivity conjecture
• Erdős-Szekeres theorem for cyclic permutations
• On meteors, earthworms and wimps
• The most and the least avoided consecutive patterns
• Coefficients and Roots of Peak Polynomials
• The number of permutations with the same peak set for signed permutations
• Cyclic quasi-symmetric functions
• Continued fractions for permutation statistics
• Combinatorics: The Art of Counting
• A proof of the peak polynomial positivity conjecture

Cited In (3)

• Title not available (Why is that?)
• Pinnacle set properties
• Cyclic shuffle compatibility

This page was built for publication: Cyclic pattern containment and avoidance

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