Probabilistic Combinatorics

点击翻译按钮获取中文摘要

The project focuses on a number of interrelated problems, all essentially combinatorial (meaning, in particular, that they usually deal with finite structures), but with connections to other areas. Though much of the PI's work has ties to other disciplines---and some of it has had unanticipated applied consequences---the emphasis here is on what seems most interesting from a mathematical standpoint. The PI has long been interested in work that cuts across mathematical boundaries. He has had success both in applying ideas from other mathematical disciplines (algebra, geometry, topology, probability, Fourier analysis, information theory) to settle well-known combinatorial problems, and, on the other hand, in bringing combinatorial ideas to bear on problems from other areas (e.g. geometry, computer science, probability, statistical mechanics). He has---as in this project---most often been interested in simple but seemingly basic questions with histories of resisting solution, motivated especially by the idea that tackling such questions necessarily forces one to go beyond existing methods. In addition the project provides research training opportunities for graduate students.The project treats combinatorial topics representing some of the PI's main current interests, most with some probabilistic aspect. A common setting is the collection of subsets of a finite set, or (the same object viewed differently) the "Hamming cube" of binary strings of a given length. The more probabilistic questions are largely concerned with thresholds and/or dependence among events; the less probabilistic ones belong to "extremal" combinatorics. All involve notions that have been at the hearts of their respective areas for decades. For example, thresholds---roughly, the intensities at which various phenomena first appear in a random system---have been central to probabilistic combinatorics and related parts of statistical physics since about 1960, and the PI's most consistent focus in recent years. Intersection properties of set systems and isoperimetric problems (these are among the less probabilistic topics) are of similar vintage and centrality.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.