Random Combinatorial Structures

Ohio State University, The, Columbus OH

Investigators

Abstract

Around 1960 Erdos and Renyi undertook a systematic study of what they called a randomly evolving (re) graph. Starting with an empty graph on n vertices, at each discrete moment a new edge is added, its position being chosen uniformly at random among the re alternatives. The basic question is what does the random graph look like after some m edges have been inserted? They were able to give a remarkable concise asymptotic description of this evolving graph, and opened the gates to a flood of research on this and many other random graph processes. Today random graph theory is a thriving area of probabilistic combinatorics that has found many applications in statistical physics (percolation), physical chemistry and theoretical computer science. Quite remarkably, random graph models have become indispensable for the analysis of probabilistic models of growing information (social) networks. The proposer will continue his work on a model of random graph (network) in which the new edges (links) tend to join the more "social" vertices (nodes), those with higher than average number of already existing links. However simple-minded, mathematical models of such graphs have a potential to become useful quantitative tools in the statistical analysis of real-life networks and they have proved to be valuable in other areas, such as polymerization theory. The proposal includes problems on other classes of random graphs, such as directed graphs in which each edge has a direction, chordal diagrams--a key notion in knot theory, threshold graphs in which the nodes are assigned weights and the edges develop only between the nodes with the total weight exceeding a threshold value, and random graphs in which each vertex degree exceeds 3. (The latter condition is basically necessary for the random graph to have a Hamilton cycle.) He will also use random graphs with restricted degrees to analyze solvability of a random system of Boolean equations. This problem belongs to a rapidly developing area of combinatorial probability and theoretical computer science that has turned out to be receptive to strikingly diverse approaches, including models and methods of statistical physics. This research may contribute to development of theoretical models and mathematical techniques that can be used by researchers in various areas who confront a challenge to describe (to predict) the structural behavior of huge networks based on assumptions regarding rules of local (pairwise) interactions between the individual nodes. The proposer will use this research program to engage his graduate students and to guide their studies toward completion of their PhD degrees.