Extremal properties of randomly perturbed structures

从理论角度研究算法行为的经典方法是最坏情况分析，我们试图找到一个对任何输入都有效的算法运行时的界限。然而，许多算法在实践中工作良好，而在最坏的情况下表现不佳。这启动了平均情况分析，我们在输入的适当概率分布下查看预期运行时间。所谓的平滑分析（见[1]）旨在通过结合这两种方法来统一它们的优点：在这里，我们测量所有输入的最大期望性能，这些输入的轻微随机扰动。这种类型的分析例如被用于最大割问题的局部搜索：对于一个有边权的图G，割（V_1，V_2）的权是V_1和V_2之间的边的总权. FLIP算法从任意切割开始，通过将一个顶点移动到另一部分来迭代地增加权重，直到我们达到局部最优切割时不再可能进行改进。该算法已被证明在最坏的情况下采取指数数量的步骤，但在实践中表现得更好。后者可以通过平滑分析[2，3]的不同变体中的更好的界限来解释，并且在[3]的设置中是否可以实际获得多项式界限是一个悬而未决的问题。平滑分析是一个可能受到随机扰动图模型研究的潜在影响的领域，该模型以非常相似的方式结合了确定性和概率性元素。我们希望进一步理解这个模型，在这个模型中，我们从一个任意的稠密图开始，以随机的方式添加边。就像在经典的二项式随机图模型G（n，p）中一样，我们通常感兴趣的是找到一个图属性A的阈值函数p=p（n）。给定d>0，p是一个阈值，如果当n趋于无穷大时，min P（G \cup G（n，p '（n））满足A）对于p'= w（p）趋于1，对于p '= o（p）趋于0，其中最小值取在所有具有边密度d的n-顶点图G上，或者在更严格的版本中，取在所有具有最小度dn的G上。其中许多涉及嵌入生成子图，如（权力）汉密尔顿循环或更一般的有界度图。例如，下面的普适性问题[4]对于D>2没有解决：G \cup G（n，p）同时包含所有最大度D的生成子图的阈值是多少？该模型的Ramsey性质也被研究[5，6，7]。给定图F，H和G，我们记G->（F，H），如果G的边的每一个红-蓝着色都允许F的一个红色副本或H的一个蓝色副本。类似地G->（F，H）^v，如果G的顶点的着色也成立。然后，我们对性质G \cup G（n，p）->（F，H）和G\cup G（n，p）->（F，H）^v的阈值感兴趣。然而，这些问题的一般情况仍然没有解决;接下来的步骤可能包括解决最后剩下的只涉及团的情况，G（n，p）->（K_4，K_t）（t>4），以及顶点着色的一般情况。该项目属于EPSRC逻辑和组合学研究领域的福尔斯。

The classical way to investigate the behaviour of algorithms from a theoretical perspective is worst-case analysis where we seek to find a bound on the runtime of an algorithm that holds for any input. However, many algorithms work well in practice while performing badly in the worst cases. This initiated average-case analyses where we look at the expected runtime under a suitable probability distribution of the inputs. The so-called smoothed analysis (see [1]) aims to unite the advantages of these two approaches by combining them: Here we measure the maximum over all inputs of the expected performance on slight random perturbations of these inputs.This type of analysis has for example been used for Local Search for the Maximum-Cut Problem: For a graph G with edge weights the weight of a cut (V_1,V_2) is the total weight of the edges between V_1 and V_2. The FLIP algorithm starts with an arbitrary cut and iteratively increases the weight by moving one vertex to the other part, until no more improvements are possible when we reach a locally optimal cut. This algorithm has been shown to take an exponential number of steps in the worst case but performed better in practice. The latter may be explained by better bounds in different variants of smoothed analysis [2, 3] and it is an open question whether one can actually obtain a polynomial bound in the setting of [3].Smoothed analysis is one area that could potentially be impacted by the study of the model of randomly perturbed graphs which combines deterministic and probabilistic elements in a very similar way. We want to further the understanding of this model in which we start with an arbitrary dense graph and adds edges in a random manner.Just as in the classical binomial random graph model G(n,p), we are typically interested in finding threshold functions p=p(n) for a graph property A. Given d>0, p is a threshold if, as n goes to infinity, min P(G \cup G(n,p'(n)) satisfies A) tends to 1 for p'=w(p) and to 0 for p'=o(p) where the minimum is taken over all n-vertex graphs G with edge density d or, in a more restrictive version, all G with minimum degree dn.Thresholds for numerous properties have recently been established. Many of these were concerned with embedding spanning subgraphs such as (powers of) Hamilton cycles or more general bounded degree graphs. For instance, the following universality question [4] is unsolved for D>2: What is the threshold for G \cup G(n,p) to contain all spanning subgraphs with maximum degree D simultaneously? Ramsey properties of this model have been investigated as well [5, 6, 7]. Given graphs F, H and G we write G->(F,H) if every red-blue colouring of the edges of G admits a red copy of F or a blue copy of H. Analogously G->(F,H)^v if the same holds for colourings of the vertices of G. We are then interested in thresholds for the properties G \cup G(n,p)->(F,H) and G\cup G(n,p)->(F,H)^v. These have been established for certain combinations of prominent F and H such as cliques and cycles. However, the general case of these problems remains unsolved; next steps might include resolving the last remaining case involving only cliques, G(n,p)->(K_4,K_t) for t>4, and the general case for vertex colourings. This project falls within the EPSRC Logics and Combinatorics research area.