Extremal properties of randomly perturbed structures

点击翻译按钮获取中文摘要

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.