Problems in Combinatorics

This project focuses on two central combinatorial topics where recent breakthroughs, several by the PI and his students, offer hope of further progress on some fundamental old problems. The first topic, "balancing problems for partially ordered sets," is motivated by questions about sorting, among the most basic of algorithmic tasks; the second, "thresholds," has been central to the study of discrete random systems since its beginnings around 1960. Though much of the PI's work has ties to other disciplines---and some of it has had unanticipated applied consequences---the emphasis is usually on what seems most interesting from a mathematical standpoint. The PI has long been interested in working across mathematical boundaries. He has had success both in applying ideas from areas beyond combinatorics (e.g., algebra, geometry, topology, probability, Fourier analysis, information theory) to settle combinatorial problems, and in bringing combinatorial ideas to bear on problems from other areas (e.g., geometry, computer science, probability, statistical mechanics). As in the current work, he has usually focused on simple, basic questions with histories of resisting solution, motivated in part by the idea that success with such questions almost always forces one to go beyond existing methods. The project will involve graduate students. The project treats two combinatorial topics that are among the PI's main current interests. The first deals with a set of notorious old, algorithmically motivated "balancing" questions for partially ordered sets; here the PI and his student M. Aires have recently made striking progress, eclipsing all that was previously known in the way of general results, and introducing new methods together with an extensive list of previously unconsidered, though seemingly basic, questions. Part of the appeal of this area is the interplay of extra-combinatorial ideas (from geometry, probability, and information theory) that underlie some of the results. The second topic is "thresholds," roughly meaning the intensities at which various behaviors of interest appear in a (large) random system; these have been central to probabilistic combinatorics and related parts of statistical physics since at least Erdos and Renyi in 1960. Recent breakthroughs by the PI and others on the ``Kahn-Kalai Conjecture'' of 2008 have refocused research in this area, rendering previously formidable results easy, and offering hope for (and already a few resolutions of) problems previously considered completely out of reach. 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.