Random Combinatorial Structures

Ohio State University Research Foundation -Do Not Use, Columbus OH

Investigators

Abstract

A classic example of a combinatorial structure is a network (a graph), described as a set of nodes (vertices) connected to their neighbors by links (arcs, edges). The networks (graphs) have long been used as abstract mathematical descriptions of real-life social and technological networks. In 1960 Erdos and Renyi began studying a mathematical model of a graph with many vertices that slowly evolves in time, as one link after another is inserted between two randomly selected nodes. However idealized, this model captured a combinatorial complexity of the real networks that are poorly connected at the inception and become more and more tight as more and more pairwise links appear in a chaotic fashion. Erdos and Renyi discovered a remarkable mathematical phenomenon: for a long time the evolving graph remains split in many small connected components, and then during a relatively short time period the graph undergoes a dramatic transition which results in the appearance of a giant connected subnetwork (subgraph) that contains a positive fraction of all vertices. This pioneering work started an avalanche of research aimed at elucidating deeper feautures of the phase transition phenomenon and tracking down the likely changes in the graph structure after the giant component has appeared. This research includes a detailed study of the group of largest components at the moments when they are about to merge into a giant component. Another component of this research is to have a close look at a core of the giant component, i.e. the largest subset of vertices in that component which are connected to each other noticeably stronger than to the other vertices. The principal investigator will work on alternative random graph models that may be closer to the real-life networks. One such network is the World Wide Web. There is a body of interesting, but not rigorous, research on the networks that grow population-wise in such a way that the most connected nodes are statistically preferred as contacts by the arrivals. The proposer plans to study these network growth processes jointly with D. Aldous and A. Frieze. Other classic examples of combinatorial structures are the partitions of sets and integers. And again there are numerous illustrations of how useful and insightful these abstractions are in applications. An integer partition is a partition of a given integer into decreasing parts. A central problem is to study the structure of a partition chosen at random among all such partitions. Since the pioneering work by Erdos and Lehner, the studies by Szalay, Turan, Fristedt and this investigator resulted in discovery of a rather detailed picture (shape) of the typical partition. The investigator plans to continue his research on the random integer partitions, and to extend it to the random plane partitions, a surprisingly rich combinatorial scheme, whose probabilistic aspects have only started to emerge. The investigator plans to combine enumerational tools and the probabilistic techniques in order to study the geometric characteristics of the typical plane partitions. The random partitions have been found critically important in probabilistic studies of optimization problems. One such well known problem is to partition a given set of numbers (weights) into two groups so that the weights of two groups are as close to each other as possible. Simplicity of this problem is deceiving: there is no efficient algorithm to solve it when the set of weights is large. It is natural then to switch attention and to study computational complexity of a typical problem when the individual weights are random. In on-going joint research C. Borgs, J. Chayes and the investigator have found a parameter of the problem whose value plays a crucial role in determination of how intrinsically difficult a typical instance of the problem is. Much as the partition problem differs from the evolving random graph, there is a striking similarity between two structures: both experience a rapid transition within a surprisingly narrow window on the parameter scale. The research will continue, and the collaborators plan to broaden it, to include various other optimization problems.