Random graph structures and their scaling limits

随机图结构及其缩放限制

• 批准号: EP/N004833/1
• 负责人: Christina Goldschmidt
• 金额: $ 135.44万
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2016
• 资助国家: 英国
• 起止时间: 2016 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FN004833%2F1
• 关键词: Random; graph; structures; their; scaling

A graph is a mathematical model for a network. It consists of a collection of nodes, some of which are linked by edges. In many application areas, for example in modelling the Internet or a social network, it is natural to think of the graph as generated randomly. My proposed research is about models of random graphs and, in particular, what we may say about large instances of them.The simplest model is the Erdos-Renyi random graph (ERRG) in which there are n nodes, each pair of which is directly linked by an edge with probability p and not linked otherwise, independently for different pairs of nodes. (We may still be able to travel between two nodes which are not directly linked if there is a path of links leading through other nodes which we may use to get from one to the other; in this case, we say that the two nodes are in the same component of the graph.) One of the many fascinating features of this model is that it undergoes a phase transition, that is a huge change in quantitative behaviour for a small change in the value of the parameter p. (The term phase transition is borrowed from physics, where it is used to describe such sudden changes in physical systems, e.g. water turning into ice or vapour at 0 and 100 degrees respectively.) In the ERRG, the phase transition concerns the component sizes, which are relatively small below the critical value of p, whereas above it, there is one giant component (containing a positive proportion of the nodes) and all of the other components are again small. The most delicate behaviour occurs exactly at this critical point, where there is an intermediate size-scaling and many components of comparable size.It is natural to ask what happens to the graph as the number of nodes grows. If we simultaneously shrink the lengths of the edges then it is possible that the graph converges. This is the idea of a scaling limit; it tells us information about the macroscopic structure of the components. In earlier work, my co-authors and I were able to give a precise description of the scaling limit of the components in the critical ERRG. It is conjectured that this scaling limit should be the same for a wide range of "high-dimensional" critical random graph models which are obtained by starting from some base graph and then performing a random attack in which some proportion of the edges, chosen at random, are rendered inactive (this is known as percolation). Proving this is one of my aims.There are many random graph models which behave appreciably differently to the ER case, and their possible scaling limits are typically much more poorly understood; I will investigate these also. Another setting which is much less developed and is where the edges of the graph are directed, so that they point from one node to another. This is the natural way to model the World-Wide Web, where links point from one webpage to another, and will form another focus of my project.A tree is a graph which has a single component and no cycles. Trees have applications which range from modelling the genealogy of populations through to understanding data structures. Random trees and their scaling limits are currently a topic of intense study, and they form a key part of my project. There is a plethora of different models here arising in a variety of settings. An example which is motivated by a classical optimisation problem is the so-called minimum spanning tree (MST). Inside any connected graph, there are (usually several possible) spanning trees, which represent different ways to connect up the nodes using the smallest number of edges. If each edge has a (potentially random) cost associated for its use, and we still wish to connect all the vertices, then we are interested in finding the MST of the graph. This turns out to behave surprisingly differently to the case where we simply pick a spanning tree uniformly at random. One of my goals is to explore the range of possible behaviours in such trees.

图是网络的数学模型。它由一组节点组成，其中一些节点由边连接。在许多应用领域，例如在互联网或社交网络建模中，很自然地认为图形是随机生成的。我提议的研究是关于随机图的模型，特别是关于它们的大实例。最简单的模型是Erdos-Renyi随机图（ERRG），其中有n个节点，每对节点由一条概率为p的边直接连接，否则不连接，独立于不同的节点对。（我们仍然可以在两个不直接连接的节点之间旅行，如果有一条链接路径可以通过其他节点，我们可以使用从一个节点到另一个节点；在这种情况下，我们说这两个节点在图的同一个分量中。）该模型的许多迷人特征之一是它经历了相变，即参数p值的微小变化导致定量行为的巨大变化。（相变一词借用自物理学，用于描述物理系统中的这种突然变化，例如水分别在0度和100度时变成冰或蒸汽。）在ERRG中，相变与组件尺寸有关，在临界值p以下相对较小，而在临界值p以上，有一个巨大的组件（包含正比例的节点），所有其他组件都很小。最微妙的行为恰好发生在这个临界点上，这里有一个中等大小的缩放和许多大小相当的组件。人们很自然地会问，随着节点数量的增长，图会发生什么变化。如果我们同时缩小边缘的长度，那么图就有可能收敛。这就是缩放极限的概念；它告诉我们有关组成部分宏观结构的信息。在早期的工作中，我和我的合著者能够精确地描述临界ERRG中组件的缩放限制。据推测，这个缩放限制应该适用于广泛的“高维”临界随机图模型，这些模型是从一些基本图开始，然后执行随机攻击，其中随机选择的一些边缘比例被渲染为非活动（这被称为渗透）。证明这一点是我的目标之一。有许多随机图模型的行为与ER情况明显不同，并且它们可能的缩放限制通常更难以理解；我也会调查这些。另一种不太发达的设置是图的边被定向的地方，所以它们从一个节点指向另一个节点。这是为万维网建模的自然方式，其中链接从一个网页指向另一个网页，这将成为我项目的另一个重点。树是一种只有一个分量没有循环的图。树的应用范围从种群的谱系建模到理解数据结构。随机树及其缩放限制是目前研究的热点，也是我项目的关键部分。这里有太多不同的模型出现在不同的环境中。一个经典优化问题的例子是所谓的最小生成树（MST）。在任何连通图中，都存在（通常是几种可能的）生成树，它们表示使用最少边数连接节点的不同方法。如果每条边的使用都有一个（可能是随机的）代价，而我们仍然希望连接所有的顶点，那么我们就有兴趣找到图的MST。这和我们随机选择一棵生成树的情况有惊人的不同。我的目标之一是探索这种树的可能行为范围。

项目成果

The size of the giant component in random hypergraphs: a short proof

随机超图中巨型分量的大小：一个简短的证明

• 发表时间: 2019
• 期刊: Electronic Journal of Combinatorics
• 影响因子: 0.7
• 作者: Cooley Oliver

Linear-sized independent sets in random cographs and increasing subsequences in separable permutations

随机图中的线性大小独立集和可分离排列中的递增子序列

• DOI: 10.5070/c62359179
• 发表时间: 2022
• 期刊: Combinatorial Theory
• 作者: Bassino F

The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses

凯莱公式的 Foata-Fuchs 证明及其概率用途

• DOI: 10.1214/23-ecp523
• 发表时间: 2023
• 期刊: Electronic Communications in Probability
• 影响因子: 0.5
• 作者: Addario-Berry L

The stable graph: The metric space scaling limit of a critical random graph with i.i.d. power-law degrees

• DOI: 10.1214/22-aop1587
• 发表时间: 2020-02
• 期刊: The Annals of Probability
• 作者: Guillaume Conchon--Kerjan-Guillaume-Conchon--Kerjan-1455031601;C. Goldschmidt

Bivariate fluctuations for the number of arithmetic progressions in random sets

随机集中算术级数数的双变量波动

• DOI: 10.1214/19-ejp391
• 发表时间: 2019
• 期刊: Electronic Journal of Probability
• 影响因子: 1.4
• 作者: Barhoumi-Andréani Y