Problems in probabilistic and geometric combinatorics

Yale University, New Haven CT

Investigators

Abstract

Combinatorics is an area centered around problems and applications. Some of these problems arise in the field itself and others come from other mathematical areas and from applications in other scientific fields. We present problems which in the interface between combinatorics, geometry and probability with much input from theoretical computer science and mathematical programming. We will study, also using discrete harmonic analysis, phase transition phenomena for combinatorial stochastic models and problems related to the combinatorics of simplicial and polyhedral complexes arising in geometric problems about convex sets. The research topics were selected to have potential impact in other areas of mathematics, theoretical computer science, mathematical programming, and questions regarding social choice. What causes phase transition for stochastic combinatorial models, and what is the nature of this phase transition? How to analyze the noise sensitivity of Boolean functions and how it is related to models of computations on the one hand, and to voting rules on the other? What can we infer from combinatorics of polyhedra to the performance of optimization algorithms. These are areas where theory and practice are surprisingly interlaced, and information as well as inspiration go both ways.