This proposal focuses on the evolution of patterns and structures in discrete objects. Through a series of interrelated problems, the PI investigates properties and statistics of various combinatorial structures, including permutations, involutions, matchings and set partitions. By a variant of the RSK algorithm from algebraic combinatorics, matchings and set partitions are in one-to-one correspondence with oscillating and vacillating tableaux, which are certain random walks in the Hasse diagram of the lattice of integer partitions. Recently there have been major breakthroughs in understanding the statistics of such tableaux. Many unexpected and deep connections have been obtained with such areas as representation theory and random matrix theory. The proposed research concentrates on the combinatorial properties behind these connections, in particular, on the properties of crossings and nestings in matchings and set partitions, which are natural extensions of increasing and decreasing subsequences in permutations. The PI will study the problems from the following aspects: pattern avoidance, filling of Ferrer shapes and growth diagram, generating functions, and asymptotic distribution. She will also extend the theory to general graphs, chord configurations, and filling of certain polyminos. In this research, some algorithm plays an important role in understanding the evolution of combinatorial patterns and structures. This algorithmic approach is a particular emphasis of the project.
This research is in the general area of combinatorics. One of the goals of combinatorics is to find efficient methods for arranging, enumerating, and manipulating discrete collections of objects. The proposed research is right aimed at these goals. The PI uses a combined algebraic and algorithmic approach to understand the formation and growth of discrete structures, which will help develop new methods and techniques in combinatorial theory. The proposed research are closed connected to other areas of mathematics, including analysis, representation theory, random matrix theory, and free probability theory. Results from this project would have direct applications in computer sciences, electronic engineering, operation research, and statistics.
