Random Graphs: Structure and Algorithms

主要研究人员：弗雷兹，艾伦建议编号：DMS-0753472机构：卡内基-梅隆大学标题：随机图：结构和算法随机组合结构的研究已成为离散数学的重要组成部分。研究最深入的领域是随机图的研究，这一领域的许多结果已经扩展到超图或集合系统。这一建议旨在研究随机图和超图的各种结构性质。此外，该提案还将考虑一些相关的算法问题。图形和网络正在成为重要的现象。网络出现在社交环境中，例如万维网中页面之间的链接。它们也出现在生物系统中，例如细胞的蛋白质相互作用网络。这些网络产生于“随机过程”，因此对随机图的研究变得越来越重要。最后，对典型图的算法研究有望有助于消除复杂性理论负面结果的阴影。

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.