The proposal is in the area of algebraic combinatorics, with six main research topics. The first topic concerns a new formula for the values of irreducible characters of the symmetric group. This formula is connected with another formula of Kerov which is not well understood, though it has applications to free probability theory and other areas. The second topic deals with a generalization of the classical theory of lattice paths on the plane, where now the paths lie on a Riemann surface. The third topic concerns the subject of sign-balance, i.e., the difference between the number of even and number of odd permutations in certain sets of permutations. The primary focus is on a conjecture of Eremenko and Gabrielov that may be connected with recent work on ribbon Schur functions. The fourth topic concerns the saturation conjecture for Littlewood-Richardson coefficients, recently proved by Knutson-Tao and others. There are many new avenues of investigation opened up by recent work in this area. The fifth topic is the theory of k-triangulations, a generalization of ordinary triangulations of a polygon. A recent breakthrough of Jakob Jonsson suggests several new open problems and conjectures. Finally the proposer plans to continue his research on increasing and decreasing subsequences, another subject for which recent work has suggested a host of new directions of research.
The proposal deals with a number of topics in algebraic combinatorics, a field which connects arrangements and patterns (such as jigsaw puzzles, computer chip design, and airplane boarding systems) with sophisticated abstract techniques. This combination of both simple, concrete objects with powerful, abstract reasoning has led to many important breakthroughs and applications. The proposer plans to work in six specific areas in which recent work points to the possibility of much further progress. These areas involve such ideas as using symmetry to simplify complicated objects, extending the notion of paths on a plane surface, decomposing a geometric figure into simpler pieces, and finding patterns in a list of objects. Progress on these very natural questions should have many applications, both within mathematics and to practical problems of scheduling, ranking, optimization, etc.
The project dealt with topics in the areas of combinatorics, algebra, and geometry. Twenty-nine findings were obtained by the proposer and his students. Several of these findings were concerned with applications of probability theory to combinatorics, such as properties of random permutations. A new random walk on permutations was analyzed (in collaboration with Rosena Du) using algebraic techniques (Hecke algebras). Using combinatorial techinques, new results were obtained on a well-studied random process, the asymmetric exclusion process (ASEP), in collboration with Sylvie Corteel, Dennis Stanton, and Lauren Williams. This process occurs in a number of different physical contexts such as Brownian motion and non-equilibrium systems. Other findings dealt with combinatorial aspects of polytopes (a higher dimensional generalization of three-dimensional polyhedra such as the cube and dodecahedron). In particular, many combinatorial problems can be formulated in terms of counting certain points (lattice points) inside polytopes. A number of computations of this sort were carried out in collaboration with some of the proposer's students (Hoda Bidkhori, Denis Chebikin, Karola Meszaros, Nan Li, Pavlo Pylyavskyy). A further topic was symmetric functions, with applications to the subject of symmetry. In the area of symmetric functions, the proposer made a conjecture, later proved by Valentin Feray, that was shown to have many applications to the "typical" shape of certain random large objects. A number of results were also obtained on partially ordered sets. These are natural structures that arise when one has only partial information on the ranking of objects. For instance, an important class of partially ordered sets that unify many combinatorial objects are called differential posets (because they are closely related to an operator that is analogous to the derivative in differential calculus). The proposer in collaboration with Fabrizio Zanello obtained new restrictions on the possible structure and size of a differential poset.
