Random Graphs: Structure and Algorithms

主要研究者：Frieze，Alan 提案编号：DMS - 0753472机构：Mellon University题目：Random Graphs：Structure and Structures随机组合结构的研究已经成为离散数学的一个重要组成部分。最激烈的研究领域是随机图，这一领域的许多成果已被扩展到超图或集系统。本文旨在研究随机图和超图的各种结构性质。此外，该提案将考虑一些相关的算法问题。图和网络正在成为重要的现象。网络出现在社交环境中，例如万维网中页面之间的链接。它们也出现在生物系统中，如细胞的蛋白质相互作用网络。这些网络源于“随机过程”，因此对随机图的研究变得越来越重要。最后，研究典型图上的算法将有望有助于消除复杂性理论负面结果的阴影。

ABSTRACTPrincipal Investigator: Frieze, Alan Proposal Number: DMS - 0753472 Institution: Carnegie-Mellon UniversityTitle: Random Graphs: Structure and AlgorithmsThe 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.