Marshall University Math Colloquium
September 29, 2015
Nick Loehr
Virginia Tech
Abstract
Mathematics is filled with open (unsolved) problems, ranging from deep foundational issues of physics, computation, geometry, and number theory to highly specialized research questions. This talk describes an open problem in algebraic combinatorics that can be stated and investigated with virtually no mathematical background, although the problem appears to be fiendishly challenging to solve. We define a family of maps on words, called “sweep maps.” A sweep map assigns a level to each letter in a word according to a simple rule, then sorts the letters according to their level. Surprisingly, although sweep maps act by sorting, they appear to be invertible: i.e., different input words are always sent to different output words by any given sweep map. The open problem is to prove the invertibility of all sweep maps, preferably by explicitly describing the inverse functions. We explain some known special cases of this problem using a model in which words are visualized using lattice paths. In some cases, we can pass from a lattice path to an associated “bounce path,” which provides the additional data needed to invert the sweep map. These bounce paths originally arose in the study of objects called q,t-Catalan polynomials. Many algorithms that have appeared in the q,t-Catalan literature over the last 20 years turn out to be particular instances of the sweep maps or their inverses. The sweep maps thus provide a simple unifying framework for understanding all of these algorithms.