Forest-Like Permutations
By Mireille Bousquet-M'elou, S. Butler. 2006
73 citations recorded by the source corpus.
Abstract.Given a permutation $$\pi \in {{\mathcal{S}}}_{n}$$, construct a graph Gπ on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if Gπ is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties).We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which Gπ is a tree, or a path, and recover the known generating function of smooth permutations.
Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/6d5f70d568439609058654f90c1aa0377cbed7b4
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algebra and Number Theory
In Discrete Mathematics and Combinatorics
In Mathematical Physics
Citations in the corpus
- Unlabeled (2+2)-free posets, ascent sequences and pattern avoiding permutations (2008, background): “We find it appropriate to mention a paper of Bousquet-Mélou and Butler [4], where the set of dots of the diagram of any permutation π is seen as a poset under the standard product order on N(2).”
- When is a Schubert variety Gorenstein (2004, methodology): “Butler [7] have used this proposition to give a characterization of locally factorial Schubert varieties in terms of Bruhat-resticted pattern avoidance.”