Refined quicksort asymptotics

The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of n data, permuted uniformly at random, the appropriately normalized complexity Y_n is known to converge almost surely to a non‐degenerate random limit Y. This assumes a natural embedding of all Y_n on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown: where denotes a standard normal random variable. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 346–361, 2015     

Acyclic edge colourings of graphs with large girth

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every , there exists a such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 511–533, 2017     

Maximum‐size antichains in random set‐systems

We show that, for , the largest set in a p‐random sub‐family of the power set of containing no k‐chain has size with high probability. This confirms a conjecture of Osthus. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 308–321, 2016     

How does the core sit inside the mantle?

The k‐core, defined as the maximal subgraph of minimum degree at least k, of the random graph has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold d_k for the appearance of an extensive k‐core. The aim of the present paper is to describe how the k‐core is “embedded” into the random graph in the following sense. Let and fix . Colour each vertex that belongs to the k‐core of in black and all remaining vertices in white. Here we derive a multi‐type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k‐core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2‐core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k‐core. Based on this the study of the k‐core reduces to the analysis of Warning Propagation on a suitable Galton‐Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 459–482, 2017     

Minimum spanning acycle and lifetime of persistent homology in the Linial–Meshulam process

This paper studies a higher dimensional generalization of Frieze's ‐limit theorem on the d‐Linial–Meshulam process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in . © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 315–340, 2017     

Random walks on stochastic hyperbolic half planar triangulations

We study the simple random walk on stochastic hyperbolic half planar triangulations constructed in (Angel and Ray, Ann Probab, in press). We show that almost surely the walker escapes the boundary of the map in positive speed and that the return probability to the starting point after n steps scales like © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 213–234, 2016     

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph . In this model G is drawn uniformly from graphs with vertex set [n], m edges and minimum degree at least three. We focus on the case where m = cn for constant c. If c is sufficiently large then our algorithm runs in time and succeeds w.h.p. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 73–98, 2015     

Almost‐spanning universality in random graphs

A graph G is said to be ‐universal if it contains every graph on at most n vertices with maximum degree at most Δ. It is known that for any and any natural number Δ there exists such that the random graph G(n, p) is asymptotically almost surely ‐universal for . Bypassing this natural boundary, we show that for the same conclusion holds when . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 380–393, 2017     

Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph G of minimum degree at least k, let G_p be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if for a function that tends to infinity as k does, then G_p asymptotically almost surely contains a cycle (and thus a path) of length at least , and (ii) if , then G_p asymptotically almost surely contains a path of length at least k. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking G to be the complete graph on k + 1 vertices. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015     

On random k‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph with large minimum degree. We fix a positive integer k and let G_k be the random subgraph where each independently chooses k random neighbors, making kn edges in all. When the minimum degree then G_k is k‐connected w.h.p. for ; Hamiltonian for k sufficiently large. When , then G_k has a cycle of length for . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function (or ) where . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017     

Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs

In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non‐maximum matching on graph G there exist an augmenting path with a length of at most 2l + 1 then the auction algorithm converges after N ? l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability and c > 1 is w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with processors and shared memory with an expected time complexity of . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384–395, 2016     

The cutoff phenomenon for random birth and death chains

For any distribution π on , we study elements drawn at random from the set of tridiagonal stochastic matrices K satisfying for all . These matrices correspond to birth and death chains with stationary distribution π. We analyze an algorithm for sampling from and use results from this analysis to draw conclusions about the Markov chains corresponding to typical elements of . Our main interest is in determining when certain sequences of random birth and death chains exhibit the cutoff phenomenon. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 287–321, 2017     

The time of graph bootstrap percolation

Graph bootstrap percolation, introduced by Bollobás in 1968, is a cellular automaton defined as follows. Given a “small” graph H and a “large” graph , in consecutive steps we obtain from G_t by adding to it all new edges e such that contains a new copy of H. We say that G percolates if for some , we have G_t = K_n. For H = K_r, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollobás and Morris considered graph bootstrap percolation for and studied the critical probability , for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time t for all © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 143–168, 2017     

On the threshold for the Maker‐Breaker H‐game

We study the Maker‐Breaker H‐game played on the edge set of the random graph . In this game two players, Maker and Breaker, alternately claim unclaimed edges of , until all edges are claimed. Maker wins if he claims all edges of a copy of a fixed graph H; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an H‐game is given by the threshold of the corresponding Ramsey property of with respect to the graph H. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 558–578, 2016     

A tail bound for read‐k families of functions

We prove a Chernoff‐like large deviation bound on the sum of non‐independent random variables that have the following dependence structure. The variables are arbitrary [0,1]‐valued functions of independent random variables , modulo a restriction that every X_i influences at most k of the variables . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99–108, 2015     

The threshold for d‐collapsibility in random complexes*

In this paper we determine the threshold for d‐collapsibility in the probabilistic model X_d(n,p) of d‐dimensional simplicial complexes. A lower bound for this threshold was established in (Aronshtam and Linial, Random Struct. Algorithms 46 (2015) 26–35), and here we show that this is indeed the correct threshold. Namely, for every c > η_d, a complex drawn from is asymptotically almost surely not d‐collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260–269, 2016     

Subgraph statistics in subcritical graph classes

Let H be a fixed graph and a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series‐parallel graphs. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 631–673, 2017     

The Brownian plane with minimal neck baby universe

For each , let be a uniform rooted quadrangulation, endowed with an appropriate measure, of size n conditioned to have r(n) vertices in its root block. We prove that for a suitable function r(n), after rescaling graph distance by converges to a random pointed non‐compact metric measure space , in the local Gromov‐Hausdorff‐Prokhorov topology. The space is built by identifying a uniform point of the Brownian map with the distinguished point of the Brownian plane. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 729–752, 2017     

Uniform multicommodity flows in the hypercube with random edge‐capacities

We give two results for multicommodity flows in the d‐dimensional hypercube with independent random edge‐capacities distributed like a random variable C where . Firstly, with high probability as , the network can support simultaneous multicommodity flows of volume close to between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437–463, 2017     

Cliques in dense inhomogeneous random graphs

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant of the Erd?s–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of for each fixed n , and give examples of graphons for which exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016 © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017