Concentration, Relaxation and Mixing time for Restricted Lattices (19frg225)


(Georgia Institute of Technology)

Louigi Addario-Berry (McGill University)

(Paris 6 University)

Sergey Bobkov (University of Minnesota)


The Banff International Research Station will host the "Concentration, Relaxation and Mixing time for Restricted Lattices" workshop in Banff from May 19, 2019 to May 26, 2019.

Card shuffling has long fascinated mathematicians, magicians and the general public alike. While mathematicians now understand and can explain many aspects of shuffling a deck of cards to great detail, they/we are stumped when it comes to a rigorous understanding of shuffling other similar combinatorial structures -- for example, the so-called 312-avoiding permutations, enumerated by the Catalan number -- or restricted subsets of well-studied spaces, as in monotone subsets of the Boolean lattice. Thus a case in study is "shuffling" a set of objects whose counting function is the famous Catalan number. The ubiquity of this number is well-documented by a recent book of Richard Stanley, with its 219 interpretations of the Catalan number.

This focused research group will attempt to solve some of the simplest-to-state, yet the most vexing and perplexing problems concerning the mixing time of specific Markov chains and the probabilistic and combinatorial structures of the corresponding state spaces; these include random walks on restrictions of the hypercube (or the Boolean lattice) and the non-crossing partition lattice. The topic is at the intersection of probability (Markov chains, free probability), statistics (random sampling and estimation), enumerative combinatorics, and theoretical computer science (property testing and randomized algorithms).

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).