Parking Functions, Stack-Sortable Permutations, and Spaces of Paths in the Johnson Graph

Abstract

We prove that the space of possible final configurations for a parking problem is parameterized by the vertices of a regular Bruhat graph associated to a 231-avoiding permutation, and we show how this relates to parameterizing certain spaces of paths in the Johnson graph.