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）趋于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的阈值。这些已经被建立为某些显著的F和H的组合，如团和循环。然而，这些问题的一般情况仍未得到解决；接下来的步骤可能包括解决最后剩下的只涉及团的情况，G(n,p)->(K_4,K_t) for t b> 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.