Probabilistic and Extremal Combinatorics

概率和极值组合学

• 批准号: 1600742
• 负责人: Bela Bollobas
• 金额: $ 40.5万
• 依托单位: University of Memphis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600742&HistoricalAwards=false
• 关键词: Probabilistic; Extremal; Combinatorics

Random geometric graphs can be used to model many large scale networks, such as the Internet and social networks. Such graphs are particularly suited to the modeling of large-scale sensor and transceiver networks, which are becoming more common as electronic devices become smaller and cheaper and are interconnected in very large networks. Modeling the behavior of these networks is becoming more and more important, and the analysis of the behavior of these networks when they become extremely large is becoming increasingly relevant in practical applications. This award supports research on the properties of these large-scale networks, as well as training of graduate students and early-career researchers in the mathematics of random graphs. The study of random geometric graphs originated with questions about the way fluids seep through porous media. More recently, the study of large-scale electronic and communication networks has prompted many questions about random geometric graphs. The basic model of random geometric graphs was proposed by Gilbert over fifty years ago: take points randomly in the plane according to a Poisson point process of unit intensity, and join two whenever they are within a prescribed distance of each other. The central question concerning this model is: for what values of the prescribed distance do we obtain an infinite connected component? Surprisingly, even after fifty years, only rough upper and lower bounds are known for the critical value of the prescribed distance. Some properties of this Gilbert model are known, but many other questions still remain unanswered. This research project addresses some of these questions, as well as other questions about related models of random graph inspired by both percolation theory and large-scale communication networks.

随机几何图可以用来模拟许多大规模的网络，如互联网和社会网络。这种图形特别适合于大规模传感器和收发器网络的建模，随着电子设备变得越来越小，越来越便宜，并且在非常大的网络中相互连接，这些网络变得越来越普遍。对这些网络的行为进行建模变得越来越重要，分析这些网络在变得非常大时的行为在实际应用中变得越来越重要。该奖项支持对这些大规模网络特性的研究，以及对研究生和早期职业研究人员在随机图数学方面的培训。随机几何图形的研究起源于流体在多孔介质中渗透的问题。最近，对大规模电子和通信网络的研究引发了许多关于随机几何图的问题。随机几何图的基本模型是五十多年前吉尔伯特提出的：在平面上按单位强度的泊松点过程随机取点，当两个点之间在规定距离内时将它们连接起来。该模型的核心问题是：对于规定距离的什么值，我们可以获得无限连接分量？令人惊讶的是，即使在五十年后，对于规定距离的临界值，只知道大致的上限和下限。吉尔伯特模型的一些特性是已知的，但许多其他问题仍未得到解答。本研究项目解决了其中的一些问题，以及受渗透理论和大规模通信网络启发的随机图相关模型的其他问题。