Random Graphs: Structure and Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

ABSTRACT Principal Investigator: Frieze, Alan Proposal Number: DMS - 0753472 Institution: Carnegie-Mellon University Title: Random Graphs: Structure and Algorithms The study of random combinatorial structures has emerged as an important component of Discrete Mathematics. The most intensely studied area is that of random graphs and many of the results of this area have been extended to hypergraphs or set systems. This proposal is aimed at doing research into various structural properties of random graphs and hypergraphs. In addition the proposal will consider some related algorithmic questions. Graphs and networks are emerging as important phenomena. Networks arise in social contexts such as links between pages in the World Wide Web. They also arise in biological systems such as the protein inter-action network of a cell. These networks arise from "random processes" and so the study of random graphs is becoming more and more relevant. Finally, studying algorithms on typical graphs will hopefully be usefull in drawing back the shadow of the negative results of complexity theory.