Evacuation of labelled graphs

DOI10.1016/0012-365X(92)00569-DMaRDI QIDQ1336658zbMATH OpenWikidataFDO

Authors Claudia Malvenuto, Christophe Reutenauer

Publication date 18 April 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)00569-D

zbMATH Keywords

evacuationlabelled graphs

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Combinatorial aspects of representation theory (05E10) Combinatorics of partially ordered sets (06A07)

Review text

In this note, Schützenberger's notion of evacuation of Young tableaux [\textit{M. P. Schützenberger}, Math. Scand. 12, 117-128 (1963; Zbl 0216.302)] and of naturally labelled posets [\textit{M. P. Schützenberger}, Discrete Math. 2, 73-94 (1972; Zbl 0279.06001)] are extended to labelled graphs. It is shown that evacuation is an involution, and that in the dual evacuation, tracks and trajectories are interchanged.

Recommendations

• An affine generalization of evacuation
• An affine generalization of evacuation
• Canonical bases and self-evacuating tableaux
• Promotion and evacuation
• Evacuation and a geometric construction for Fibonacci tableaux

Cites work

• Balanced tableaux
• Dual equivalence with applications, including a conjecture of Proctor
• scientific article; zbMATH DE number 3587058 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Promotion des morphismes d'ensembles ordonnes
• Quelques remarques sur une Construction de Schensted.

Cited in

(20)

• Promotion and evacuation
• Fixed points of the evacuation of maximal chains on fuss shapes
• Polyurethane toggles
• Combinatorial Markov chains on linear extensions
• Distributed Evacuation in Graphs with Multiple Exits
• Toric promotion
• Upper Bounds on Mixing Time of Finite Markov Chains
• Markov Chains for Promotion Operators
• Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
• Random shuffles on trees using extended promotion
• An affine generalization of evacuation
• Effective Poset Inequalities
• Promotion sorting
• Linear extensions and shelling orders
• Bender-Knuth involutions on linear extensions of posets
• Permutoric promotion: gliding globs, sliding stones, and colliding coins
• On the cross-product conjecture for the number of linear extensions
• Bender-Knuth billiards in Coxeter groups
• Properties of the promotion Markov chain on linear extensions
• Toric and permutoric promotion

This page was built for publication: Evacuation of labelled graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336658)