Let [u,v] be a Bruhat interval and B(u,v) be its corresponding Bruhat graph. The combinatorial and topological structure of the longest u-v paths of B(u,v) has been extensively studied and is well-known. Nevertheless, not much is known of the remaining paths. Here we describe combinatorial properties of the shortest u-v paths of B(u,v). We also derive the non-negativity of some coefficients of the complete cd-index of [u,v].
Résumé. Soit [u,v] un intervalle de Bruhat et B(u,v) le graphe de Bruhat associé. La structure combinatoire et topologique des plus longs chemins de u à v dans B(u,v) est bien comprise, mais on sait peu de chose des autres chemins. Nous décrivons ici les propriétés combinatoires des plus courts de chemins de u à v. Nous prouvons aussi que certains coefficients du cd-indice complet de [u,v] sont positifs.