Random Structures and Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The project deals with the likely properties of randomly chosen discrete mathematical objects. It deals with them from an aesthetic and a computational angle. In many cases the objects are networks and the project aims to learn the typical values of various associated parameters. One particular example of this concerns the length of the largest cycle in a randomly chosen graph. One question the PI hopes to resolve is the following: suppose we only sample from networks where each vertex is incident with at least three edges. How many random edges are needed so that with high probability there is a cycle that goes through each vertex once and only once i.e. a Hamilton cycle. As a typical example of a computational problem consider the following: the edges of a network are given random weights and one wishes to find a minimum weight spanning tree i.e. a set of edges that connects the vertices of the network. Suppose that in addition, the edges have random costs and there is a budget for the tree that cannot be exceeded. The PI provides an algorithm for this problem that with high probability finds a near optimal solution very quickly. The PI notes that with an infinite budget, the problem is easily solved, but for a finite budget, the problem is hard in the worst-case. In addition this project provides research training opportunities for graduate students. The project deals with structural and algorithmic questions associated with random graphs, hypergraphs and matrices over a finite field. The PI will try to show that a random graph with cn, c>3/2 random edges and conditioned to have minimum degree at least three, is Hamiltonian with high probability. The PI will try to simplify our asymptotic expression for the length of the longest path in a sparse random graph. the PI will attempt to answer these questions in relation to random digraphs. The PI will continue his work on analyzing minimum weighted structures in randomly edge weighted graphs, subject to constraints on a cost budget. The PI will continue his work on random walks. the PI will also try to improve his results on deterministic estimates of the covertime of dense graphs. The PI will study the rank of random matrices over finite fields, trying to explain combinatorially why the actual field does not seem to be important. The PI will also consider the binary case as an example of a random matroid. Finally, the PI will try to extend his analysis of a simple particle dispersion process from one to more than one dimension. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.