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的边连接，否则不连接，独立于不同的节点对。(We仍然可以在两个没有直接链接的节点之间旅行，如果有一条通过其他节点的链接路径，我们可以使用它从一个节点到达另一个节点;在这种情况下，我们说这两个节点在图的同一个组件中。这个模型的许多吸引人的特征之一是它经历了相变，这是参数p值的微小变化在定量行为上的巨大变化。（术语相变是从物理学中借用的，它被用来描述物理系统中的这种突然变化，例如水分别在0度和100度变成冰或蒸汽。）在ERRG中，相变涉及组件的大小，这是相对较小的临界值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