Binary operations on pattern-avoiding cycles

Abstract

Suppose $c_n(\ddot{I}ƒ)$ denotes the number of cyclic permutations in ${\mathcal{S}}_n$ that avoid a pattern $\ddot{I}ƒ$. In this paper, we define partial groupoid structures on cyclic pattern-avoiding permutations that allow us to build larger cyclic pattern-avoiding permutations from smaller ones. We use this structure to find recursive lower bounds on $c_n(\ddot{I}ƒ)$. These bounds imply that $c_n(\ddot{I}ƒ)$ has a growth rate of at least 3 for $\ddot{I}ƒ\in \{231,312,321\}$ and a growth rate of at least 2.6 for $\ddot{I}ƒ\in \{123,132,213\}$. In the process, we prove (and sometimes improve) a conjecture of Bóna and Cory that $c_n(\ddot{I}ƒ)\ge 2c_{n-1}(\ddot{I}ƒ)$ for all $\ddot{I}ƒ\in {\mathcal{S}}_3\setminus \{123\}$ and $n\ge 2.$