Forest-like permutations
| dc.creator | Bousquet-Mélou, Mireille | |
| dc.creator | Butler, Steven | |
| dc.date | 2006-03-27 | |
| dc.date | 2006-06-26 | |
| dc.date.accessioned | 2026-07-07T09:36:46Z | |
| dc.date.available | 2026-07-07T09:36:46Z | |
| dc.description | Given a permutation $π\in \Sn\_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, this shows 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. | |
| dc.identifier | https://arxiv.org/abs/math/0603617 | |
| dc.identifier | http://arxiv.org/abs/math/0603617 | |
| dc.identifier | Annals of Combinatorics 11 (2007) 335--354 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160236 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A15, 14M15 | |
| dc.title | Forest-like permutations | |
| dc.type | text |