A large part of mathematics deal with the general question of studying important parameters of a natural combinatorial structure A. Here are few examples:
(1) A= a graph. Parameters: chromatic numbers, number of triangles, number of hamiltonian cycles etc.
(2) A= a polytope. Parameters: number of vertices, number of facets, the volume etc.
(3) A= a permutation. Parameters: number of cycles, length of the longest increasing subsequence etc.
Now imagine that the object A is sampled from some distribution. All parameters above and many others become random variables, and it is natural to study basic questions one usually asks in probability: what is the expectation, variance, degree of concentration, limiting distribution etc ? These problems form the foundation of the theory of random combinatorial structures. Among the above examples, perhaps Random graphs is the richest topic, and there are two good textbooks under this very same title (by Bollobas and Janson-Luczak-Rucinski) that might serve as introduction. For random polytopes see this survey by Schneider. I spent a fair amount of time working on random graphs and random polytopes.
Representative publications:
(1) A. Johansson, J. Kahn and V. Vu, Factors in random graphs, Random Structures and Algorithms, 2008.
It is well known that a random graph has a perfect matching (with high probability) once the edge density become log n (which guarantees that each vertex has at least one neighbor, with high probability). The hypergraph version of this, known as Shamir conjecture, was a central open problem in the field for more than two decades. The main reason for the difficulty here is that there is no efficient Hall theorem (which is a major tool for studying perfect matching in graphs) for hypergraphs.
In (1), we developed a general approach which not only solves Shamir problem, but the factoring problem in the most general setting, obtaining solution to many other problems such as Erdos’ and Alon-Yuster’s.
(2) J. H. Kim and V. Vu, Sandwiching random graphs, Advances in Mathematics 188 (2004) 444-469.
In (2), we studied the notion of universality for random graphs. Given a random regular graph with degree d and a random Erdos-Renyi graph with average degree d (or edge density d/n), we expect that these two models behave the same way. However, this is not true if d is small (a constant, say), as in this case, the regular constrain has a significant impact that forces the random regular graph be connected. We manage to show, though, that for d tending to infinity and not too large (d^3 < n), the two models can be directly coupled, so that one graph can be obtained from the other by changing only few edges at each vertex. This way, one can derive many asymptotic properties of one model from the other in a simple manner. This paper also leads to the notion of resilience which is of interest on its own right; see for instance here. We conjecture that the assumption d^3 < n can be removed.
(3) V. Vu, Sharp concentration of random polytopes GAFA (2005), no 6, 1284-1328.
A random polytope P_n is generated as the convex hull of a set of n random points sampled uniformly from a convex set K of volume 1. We study the basic question: how does the volume (number of vertices, number of facets etc) of P_n behave as a random variable ?
Using a technique called “divide and conquer” martingale, we give sharp concentration bounds for the above parameters, which implies sharp upper bound for moments of all fixed order. Matching lower bounds are given by Reizner. In follows up papers (see here, here and here) these bounds are used to prove central limit theorem for parameters in questions for the case K has nice boundary.
Few favorite open problems.
(A) Let X be the chromatic number of the random graph G(n,1/2). What is the limiting distribution of X ? It is not known if it has one. The asymptotic of X was computed by Bollobas in the 80s using a beautiful martingale argument.
(B) Let G(n,d) be the random regular graph of degree d. Prove that the second
largest singular value of G(n,d) is O(d^{1/2}). This is known to hold in the case d < n^{1/2}, thank to the method introduced by Kahn and Szemeredi. For d=n/2, the best bound known has an extra log term. For constant d, Friedman, in a tour-de-force paper, obtained a precise asymptotic bound, confirming a conjecture of Alon.
(C) Prove the CLT for the volume of random polytopes considered in (3). The CLT mentioned in (3) needs some assumption on the boundary of K, but it is conjectured that CLT holds for general K. This was confirm in the two dimensional case recently by J. Pardon.