Bijective Approach to Discrete Geometries

Brandeis University, Waltham MA

Investigators

Abstract

Combinatorics is a central branch of mathematics concerned with the description and analysis of discrete data structures. Combinatorialists try to uncover patterns and building blocks in such structures, in order to explain their global behavior. Combinatorial tools are therefore of central importance in many other fields of science, such as computer science, statistical mechanics, statistics, and probability. This project focuses on the encoding of several discrete geometrical structures (planar graphs, polytopal decompositions of space, etc.) by simpler mathematical structures. Such an encoding, which provides a genuinely different description of the same structures, can greatly simplify the analysis of the objects under consideration. Indeed, certain patterns and probabilistic behavior which were hidden in the original description, may appear more clearly in the alternative description. This projects aims to develop bijective tools in order to solve several fundamental open problems in combinatorics, with motivations coming from probability, theoretical physics, and computer science. One of the major goals is to set the foundation for a multi-authored proof of a deep relation between three very important probabilistic constructions: random planar graphs, the Gaussian free field, and SLE curves. The proof will be built upon a bijective encoding of percolation-endowed planar triangulations by some two-dimensional lattice walks. Other goals of this project are related to proper coloring of graphs (explaining bijectively a counting formula for properly colored planar graphs), integrable system approach to the symmetric group ("diagonalizing" the KP differential equations governing the factorizations in the symmetric group), hyperplane arrangements (bijections for the faces of the deformations of the Coxeter arrangement), and graph drawing algorithms (simultaneous generalization of Schnyder woods and transversal structures). 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.