2413-balloon permutations and the growth of the Möbius function (Q2288170)

The set of all permutations (written as words), together with the ordering \(\sigma \leq \pi\) if \(\pi\) contains the pattern \(\sigma\), defines a partially ordered set (poset). The principal Möbius function \(\mu[\pi]\) is the value of \(\mu[1,\pi]\) where \(\mu\) is the ordinary Möbius function of the poset. This article shows that the principal Möbius function grows exponentially in the length of \(\pi\). More precisely, the author proves that for all \(n\), \[ \max\{|\mu[\pi]| : |\pi| = n\} \geq 2^{\lfloor n/4\rfloor -1}. \] To prove this result, the author defines an operation called ballooning, denoted by \(\circledcirc\), which can be thought of informally as inserting a permutation into the ``center'' of the permutation \(2413\). The author shows that for a permutation \(\pi\) of the form \(\pi = 2413 \circledcirc \sigma\), where \(\sigma\) itself is a \(2413\)-balloon, then \(\mu(\pi) = 2\mu(\sigma)\). The exponential growth of the principal Möbius function follows by recursively defining a permutation of length \(n\), verifying a small number of initial cases, and applying induction. In fact, the author proves that if \(\sigma\) is not \(1\), \(2413\), or a \(2413\)-balloon, then \(\mu[2413 \circledcirc \sigma] = \mu[\sigma]\). The article concludes with a generalization of ballooning and provides several questions and conjectures.