Publications

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order (log n)2, speeding up the mixing to order logn. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erd˝os-Rényi graph is logarithmic.

We extend a recent argument of Kahn, Narayanan and Park ((2021) Proceedings of the AMS 149 3201-3208) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of C4 that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning Kr-cycles.

A classical result by Rado characterises the so-called partition-regular matrices A, i.e. those matrices A for which any finite colouring of the positive integers yields a monochromatic solution to the equation Ax=0. We study the asymmetric random Rado problem for the (binomial) random set [n]p in which one seeks to determine the threshold for the property that any r-colouring, r≥2, of the random set has a colour i∈[r] admitting a solution for the matrical equation Aix=0, where A1,…,Ar are predetermined partition-regular matrices pre-assigned to the colours involved. We prove a 1-statement for the asymmetric random Rado property. In the symmetric setting our result retrieves the 1-statement of the symmetric random Rado theorem established in a combination of results by Rödl and Ruciânski [34] and by Friedgut, Rödl and Schacht [11]. We conjecture that our 1-statement in fact unveils the threshold for the asymmetric random Rado property, yielding a counterpart to the so-called Kohayakawa-Kreuter conjecture concerning the threshold for the asymmetric random Ramsey problem in graphs. We deduce the aforementioned 1-statement for the asymmetric random Rado property after establishing a broader result generalising the main theorem of Friedgut, Rödl and Schacht from [11]. The latter then serves as a combinatorial framework through which 1-statements for Ramsey-type problems in random sets and (hyper)graphs alike can be established in the asymmetric setting following a relatively short combinatorial examination of certain hypergraphs. To establish this framework we utilise a recent approach put forth by Mousset, Nenadov and Samotij [26] for the Kohayakawa-Kreuter conjecture.

In this work we consider extensions of a conjecture due to Alspach, Mason, and Pullman from 1976. This conjecture concerns edge decompositions of tournaments into as few paths as possible. There is a natural lower bound for the number paths needed in an edge decomposition of a directed graph in terms of its degree sequence; the conjecture in question states that this bound is correct for tournaments of even order. The conjecture was recently resolved for large tournaments, and here we investigate to what extent the conjecture holds for directed graphs in general. In particular, we prove that the conjecture holds with high probability for the random directed graph Dn,pDn,pD_{n,p} for a large range of p.