The project's central focus is on several interrelated problems on the borders of combinatorics and probability. The questions raised spill over into other areas, such as classical asymptotic enumeration, algebraic topology, and probability proper. One major theme of the project is the effort to understand the "threshold" intensities at which various properties of interest appear in (large) discrete random systems. This is a classical area (going back to the beginnings, roughly 60 years ago, of studies of random graphs on the combinatorial side and percolation on the probabilistic); but it is also an area that has seen major progress in recent years, and one that enjoys close ties with several other disciplines, including statistical physics and the theory of computation. Though the questions under study are purely mathematical, work in this subject area has sometimes had quite unforeseen consequences, both in and beyond mathematics. This research project centers on simple and seemingly basic questions with "pedigrees," that is, substantial histories of resisting solution. Attacking such questions is a way of forcing oneself to go beyond existing methods, which often leads to finding and exploiting new connections with other parts of mathematics and related areas.
Several of the main problems under study are concerned with understanding the extent to which various classical facts and theorems remain true in a random setting; for example: (a) When (i.e., for what p = p(n)) is the "clique complex" (whose simplices are the vertex sets of the cliques) of the random graph G(n,p) likely to have vanishing k-dimensional homology (e.g., over the integers or the integers mod 2)? (b) When does a random collection F of k-subets of an n-set X have the ("Erdos-Ko-Rado") property that a largest subcollection not containing two disjoint sets consists of the members of F containing some fixed element of X? In these and other cases, further progress appears to depend on better understanding underlying issues of independent interest. The proposal also suggests some very general possibilities, for example, one on behavior of independent events as a guide to more complicated situations, and another (due to Kalai and the PI) which would in principle determine (up to an unavoidable logarithmic error factor) the threshold for a completely arbitrary increasing property (of subsets of some finite universe; the "threshold" being, roughly speaking, where the property goes from unlikely to likely). Though most of the headline problems are of probabilistic-combinatorial origin, there are substantial connections with other areas --- some combinatorial, others, particularly when it comes to methodology, more distant; for instance: (a) the proof of an old conjecture on presence of certain trees in a random graph eventually depended (very much inter alia) on developing precise estimates for a sampling-without-replacement version of classical renewal theory; (b) the currently most promising line of attack on the general threshold conjecture mentioned above is more Fourier-analytic than combinatorial and originates (though much has happened since) in work of the PI and coauthors nearly thirty years ago on a problem from theoretical computer science.
