We describe edge labelings of the increasing flip graph of a subword complex on a finite Coxeter group, and study applications thereof. On the one hand, we show that they provide canonical spanning trees of the facet-ridge graph of the subword complex, describe inductively these trees, and present their close relations to greedy facets. Searching these trees yields an efficient algorithm to generate all facets of the subword complex, which extends the greedy flip algorithm for pointed pseudotriangulations. On the other hand, when the increasing flip graph is a Hasse diagram, we show that the edge labeling is indeed an EL-labeling and derive further combinatorial properties of paths in the increasing flip graph. These results apply in particular to Cambrian lattices, in which case a similar EL-labeling was recently studied by M. Kallipoliti and H. Mühle.
Résumé. Nous décrivons des étiquetages d'arêtes du graphe des flips croissants d'un complexe de sous-mots sur un groupe de Coxeter fini, et nous en étudions certaines applications. D'une part, nous montrons qu'ils fournissent des arbres couvrants canoniques du graphe des flips du complexe de sous-mots, nous décrivons inductivement ces arbres, et nous présentons leurs liens étroits avec les facettes gloutonnes du complexe. Le parcours de ces arbres permet d'engendrer efficacement les facettes du complexe des sous-mots, généralisant ainsi l'algorithme de flips gloutons pour les pseudotriangulations. D'autre part, lorsque le graphe des flips croissants est un diagramme de Hasse, nous montrons que notre étiquetage d'arêtes;est lexicographique et nous en déduisons des propriétés supplémentaires du graphe des flips croissants. Ces résultats s'appliquent en particulier aux treillis Cambriens pour lesquels un étiquetage lexicographique similaire a été récemment étudié par M. Kallipoliti and H. Mühle.