Note on a problem of M. Talagrand

Answering a question of M. Talagrand, we show that there is a fixed L with the following property. For positive integers and , if is the set of subgraphs of K_n containing at least copies of K_k, then there is a set of subgraphs of K_n such that (i) each member of contains a member of and (ii) (where means number of edges). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 663–668, 2015     

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     

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     

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     

Randomized rumor spreading in poorly connected small‐world networks

The Push‐Pull protocol is a well‐studied round‐robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze the behavior of this protocol on random ‐trees, a class of power law graphs, which are small‐world and have large clustering coefficients, built as follows: initially we have a ‐clique. In every step a new node is born, a random ‐clique of the current graph is chosen, and the new node is joined to all nodes of the ‐clique. When is fixed, we show that if initially a random node is aware of the rumor, then with probability after rounds the rumor propagates to nodes, where is the number of nodes and is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion and constant treewidth, these results demonstrate that Push‐Pull can be efficient even on poorly connected networks. On the negative side, we prove that with probability the protocol needs at least rounds to inform all nodes. This exponential dichotomy between time required for informing almost all and all nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound successfully carries over to a closely related class of graphs, the random ‐Apollonian networks, for which we prove an upper bound of rounds for informing nodes with probability when is fixed. Here, © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 185–208, 2016     

Group representations that resist random sampling

We show that there exists a family of groups G_n and nontrivial irreducible representations ρ_n such that, for any constant t, the average of ρ_n over t uniformly random elements has operator norm 1 with probability approaching 1 as . More quantitatively, we show that there exist families of finite groups for which random elements are required to bound the norm of a typical representation below 1. This settles a conjecture of A. Wigderson. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 605–614, 2015     

Random directed graphs are robustly Hamiltonian

A classical theorem of Ghouila‐Houri from 1960 asserts that every directed graph on n vertices with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph , that is, a directed graph in which every ordered pair (u, v) becomes an arc with probability p independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if , then a.a.s. every subdigraph of with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. The constant 1/2 is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016     

New methods to bound the critical probability in fractal percolation

We study the critical probability p_c(M) in two‐dimensional M‐adic fractal percolation. To find lower bounds, we compare fractal percolation with site percolation. Fundamentally new is the construction of a computable increasing sequence that converges to p_c(M). We prove that and . For the upper bounds, we introduce an iterative random process on a finite alphabet , which is easier to analyze than the original process. We show that and . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 710–730, 2015     

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     

Compatible Hamilton cycles in random graphs

A graph is Hamiltonian if it contains a cycle passing through every vertex. One of the cornerstone results in the theory of random graphs asserts that for edge probability , the random graph G(n, p) is asymptotically almost surely Hamiltonian. We obtain the following strengthening of this result. Given a graph , an incompatibility system over G is a family where for every , the set F_v is a set of unordered pairs . An incompatibility system is Δ‐bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F_v containing e. We say that a cycle C in G is compatible with if every pair of incident edges of C satisfies . This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be used as a quantitative measure of robustness of graph properties. We prove that there is a constant such that the random graph with is asymptotically almost surely such that for any μnp‐bounded incompatibility system over G, there is a Hamilton cycle in G compatible with . We also prove that for larger edge probabilities , the parameter μ can be taken to be any constant smaller than . These results imply in particular that typically in G(n, p) for , for any edge‐coloring in which each color appears at most μnp times at each vertex, there exists a properly colored Hamilton cycle. Furthermore, our proof can be easily modified to show that for any edge‐coloring of such a random graph in which each color appears on at most μnp edges, there exists a Hamilton cycle in which all edges have distinct colors (i.e., a rainbow Hamilton cycle). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 533–557, 2016     

A local central limit theorem for triangles in a random graph

In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos‐Rényi random graph G(n, p), where is a fixed constant. Our proof is based on bounding the characteristic function of the number of triangles, and uses several different conditioning arguments for handling different ranges of t. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 732–750, 2016     

Balls into bins via local search: Cover time and maximum load

Abstract–We study a natural process for allocating balls into bins that are organized as the vertices of an undirected graph . Balls arrive one at a time. When a ball arrives, it first chooses a vertex in uniformly at random. Then the ball performs a local search in starting from until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case , we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 681–702, 2016     

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     

Multipass greedy coloring of simple uniform hypergraphs

Let be the minimum number of edges in an n‐uniform simple hypergraph that is not two colorable. We prove that . Our result generalizes to r‐coloring of b‐simple uniform hypergraphs. For fixed r and b we prove that a maximum vertex degree in b‐simple n‐uniform hypergraph that is not r‐colorable must be . By trimming arguments it implies that every such graph has edges. For any fixed our techniques yield also a lower bound for van der Waerden numbers W(n, r). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 125–146, 2016     

Dependence and phase changes in random m‐ary search trees

We study the joint asymptotic behavior of the space requirement and the total path length (either summing over all root‐key distances or over all root‐node distances) in random m‐ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when , but becomes of higher order when . Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when , but is periodically oscillating for larger m, and we also prove asymptotic independence when . Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log‐trees such as fringe‐balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353–379, 2017     

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Given a graph on n vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colours on the edges. Similarly (for even n) a rainbow perfect matching is a collection of independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least 1 (respectively, at least 2). More precisely, consider n points (i.e. vertices) chosen independently and uniformly at random from the unit d‐dimensional cube for any fixed . Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the norm, for any fixed ). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of colours, where a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least 1 must contain a rainbow perfect matching (for even n), and the first graph with minimum degree at least 2 must contain a rainbow Hamilton cycle. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 587–606, 2017     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016     

Improved bounds for the randomized decision tree Complexity of recursive majority

We consider the randomized decision tree complexity of the recursive 3‐majority function. We prove a lower bound of for the two‐sided‐error randomized decision tree complexity of evaluating height h formulae with error . This improves the lower bound of given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of given by Leonardos (ICALP'13). Second, we improve the upper bound by giving a new zero‐error randomized decision tree algorithm that has complexity at most . The previous best known algorithm achieved complexity . The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel “interleaving” of two recursive algorithms. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 612–638, 2016     

Four random permutations conjugated by an adversary generate Sn with high probability

We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that four random permutations in the symmetric group S_n generate a transitive subgroup with probability for some independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of . In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of A_n or except for probability as . The analysis is closely related to the following random set model. A random set is generated by including each independently with probability . The sumset is formed. Then at most four independent copies of are needed before their mutual intersection is no longer infinite. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 409–428, 2016     

Edge‐disjoint Hamilton cycles in random graphs

We show that provided we can with high probability find a collection of edge‐disjoint Hamilton cycles in , plus an additional edge‐disjoint matching of size if is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 397–445, 2015