A classic example of a discrete combinatorial structure is a graph, and graph theory, including its enumerative aspect, is one of the most developed parts of combinatorics. Back in the sixties, in a series of pioneering papers Erdos and Renyi created what is now known as random graphs theory, a fast growing research area remarkable for fruitful interplay of enumerative combinatorics and modern probabilistic models and techniques. While Erdos-Renyi random graph process is based on assumption that a new edge location is chosen uniformly at random, it has been recognized that in some applications (internet networks) a more realistic assumption is of a bias toward more "popular" vertices (nodes), a so-called preferential attachment hypothesis. The proponent has proved that in this counterpart of the E-R process the random graph undergoes a rapid transformation, from a sea of small components (clusters) to a giant cluster in a sea of small clusters. The proponent plans to study the subsequent phases of the graph process, such as formation of a k-core, and the moment the graph first becomes connected. The proponent will study vertex and edge percolation processes on random graphs with a given degree distribution, and solvability of the random Boolean equations based on his previous studies of the E-R process at the critical stage. The program includes joint research with Alan Frieze ("mixing" time of a random walk on an incipient giant component of the E-R graph), and Nick Wormald (directed version of the E-R process). Among other problems are (i) a detailed asymptotic study of the expected coalescing time for a "m balls into n boxes" combinatorial scheme, motivated by problems in population genetics ("most recent common ancestor")and computer science ("coupling-from-the past" algorithm by Propp and Wilson);(ii) enumerative-probabilistic study of "sorting networks"; (iii) probabilistic study of "hard-to-solve" combinatorial problems, such as integer partitioning problem and a k-SAT problem, on satisfiability of a random Boolean function with clauses of length k > 2.
Importantly, besides its intrinsic mathematical value, the proposed research program is motivated by problems arising in related areas of operations research (two-sided labor markets), probabilistic modeling of growing information networks, percolation processes in statistical physics, and average case analysis of combinatorial algorithms. Some of these problems seem particularly suitable as research topics for the proponent's partnerships with PhD students. The past beneficiaries of such a collaboration were Adam Hammett and Craig Lennon who successfully defended their PhD theses on problems from the program funded by the NSF in 2004−2007. The proponent is confident that systematic interaction with his current students, John McSweeney and Jia Yeum, will lead to solving two problems included in the proposed program, one on the expected coalescing time for the allocation model,and another on probability of solvability of the random equations.
The goal of this project was to analyze the properties of large combinatorial structures and the random processes that describe their gradual evolution. With my doctoral student, John McSweeney, we studied an allocation process in which "balls" are repeatedly thrown into boxes, independently of each other, according to some probability distribution. At each step, all balls landing in the same box are "fused" into a single ball; the process terminates when there is only one ball left (complete coalescence). We found a sharp asymptotic formula for the expected value of complete coalescence time for a broad class of allocation probabilities, an important parameter in analysis of a random genealogical process. The PI studied the hitting times and hit locations for a Markov chain with tight transition probability rows, confirming a conjecture of Guy Louchard for a special case of these chains. As expected by Louchard, this result led to sharp asymptotic estimates of largest parts sizes in restricted random compositions of large integers. The PI continued to work on solvability of a random system of linear Boolean equations with two variables in each equation, a long-term project that started with a PhD research of the PI's other doctoral student, Ji-A Yeum. We showed that the solvability probability undergoes a rapid transition when the edge density of the underlying graph passes through a critical value 1. Prior to John McSweeney and Ji-A Yeum, my other advisees, Adam Hammett and Craig Lennon, got their PhD degrees, both in 2007. Based on their projects, there were two papers published, with Adam in Transactions of the AMS, with Craig in Combinatorics, Probability and Computing, The PI's research was supported by the preceding and the current NSF Grants. The PI continued supervising the PhD projects of Huseyin Acan and Chris Ross. With Huseyin we worked on asymptotic study of intersection graphs of the uniformly random chord diagrams on an even number of cyclically arranged points. We were able to simplify significantly a proof of Flajolet-Noy’s theorem which states that almost all diagrams are monolithic. We found a diagrammatic counterpart of Cayley's formula for the number of chordal diagrams whose intersection graph is a forest of either rooted and or unrooted trees. Chris and the PI focussed on an asymptotic study of another class of random graphs, so-called threshold graphs, recently studied by Reilly and Scheinerman, and Diaconis, Holmes and Janson. Chris was able to find the limiting distribution (marginal and joint) of the longest cycle length and the maximum matching number, the k-core size, and began working on those characteristics of bipartite threshold graphs. The PI obtained a generating-function extension of a classic inequality, due to Stepanov, for a connectedness probability of a Bernoulli subgraph of a complete graph. The bound is sufficiently strong to obtain sharp estimates of the count of sparsely-edged connected graphs. In Autumn 2009 -Winter 2010 the PI worked on a long-term project of asymptotic enumeration of strongly-connected digraphs, a problem posed by Wright back in 1977. The PI found a way to extend the "embedding" technique, developed initially with Nick Wormald for counting connected undirected graphs, to the digraphs case. The paper is forthcoming in Random Structures and Algorithms. In 2008 - 2009 the PI also worked on two revisions of a "On a random graph evolving by degrees", that was published in Advances in Mathematics in 2010. In this paper, we consider a random (multi)graph growth process, a special case of a more general process proposed by Lovasz in 2002. This process is a "preferential attachment" counterpart of the classic Erdos-Renyi process; our key result is determination of a threshold edge-density value for the birth of a "giant" component. In Spring 2010 Alan Frieze (Carnegie Mellon University) and the PI started working on a long-standing problem of almost certain "Hamiltonicity" of a random graph of the minimum degree at least three, and the number of edges barely large to be compatible with the minimum degree constraint. We derived the differential equations whose solution closely approximates a first phase of an algorithm designed to deliver a Hamilton cycle in an almost linear time. Alan and I continue our collaboration In Spring-Summer 2010 Greg Sorkin (IBM Research Center) and the PI started working on solvability probability of a random system of linear Boolean equations, each containing k > 2 variables. With aid of computer,we proved that the system of equations is likely to have a solution provided that the ratio of number of equations to the number of unknowns is below 1. Greg and I continue our collaboration. The NSF Grant gave the PI a precious opportunity to focus on research and recruiting and advising the graduate students for doing PhD studies in combinatorial probability.
