Combinatorial Probability and Representation Theory

Probability is the mathematical study of how likely an event occurs or a proposition is true. Representation theory is the study of algebraic structures by realizing their elements as linear maps on vector spaces or modules and decomposing them into their smallest constituents. Both probability and representation theory lend themselves to combinatorial analysis.

For example, in probability the events could be discrete states and in representation theory the index set of a representation is often a combinatorial object such as a partition. The main premise of this proposal is the development of new combinatorial techniques for answering fundamental questions in both probability and representation theory. This project also has a substantial computational component (contributing to and using the rapidly growing open-source mathematical software SAGEMATH).

The outcome of this research will impact areas beyond those of their original motivation. For example, it relates to invariant theory, complexity theory, and voting procedures. These investigations are fueled by extensive computational experimentation.

Robust implementation of algorithms derived from the project will lead to new, open-source code for the SAGEMATH computer algebra system. The dissemination of this new SAGEMATH software will not only advance the proposed research program, but will (and has already) cross-fertilize various areas in mathematics and computer science. In addition, the project will support a diverse group of graduate students and encourage the participation of female students and researchers.

The PI also plans to organize workshops, engage in promoting open access publishing, and disseminate results via lecture series.

The project is aimed at solving open problems on five topics in combinatorial probability and representation theory. The five proposed projects will be attacked with various teams of collaborators and include: (1) Mixing times of Markov chains using the recently developed new theory for computing stationary distributions for any finite Markov chain.

This approach uses sophisticated methods in semigroup theory. (2) A new uncrowding algorithm for hook-valued tableaux in relation to canonical stable Grothendieck polynomials in K-theory. (3) The generalization of a crystal associated to stable Grothendieck polynomials. This approach will likely yield new K-theoretic insertion algorithms. (4) Insertion algorithms for the partition algebra and its subalgebras.

The partition algebra is a centralizer algebra. New insertion algorithms are required to match the underlying representation theory in various cases. (5) Symmetric chain decompositions of crystal bases can answer questions about plethysm coefficients and have applications to physics, invariant theory and complexity theory.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.