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     

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     

Clairvoyant embedding in one dimension

Let v, w be infinite 0‐1 sequences, and a positive integer. We say that is ‐embeddable in , if there exists an increasing sequence of integers with , such that , for all . Let and be coin‐tossing sequences. We will show that there is an with the property that is ‐embeddable into with positive probability. This answers a question that was open for a while. The proof generalizes somewhat the hierarchical method of an earlier paper of the author on dependent percolation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 520–560, 2015     

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     

On induced Ramsey numbers for k‐uniform hypergraphs

Let denote the complete k‐uniform k‐partite hypergraph with classes of size t and the complete k‐uniform hypergraph of order s. One can show that the Ramsey number for and satisfies when t = s^o(1) as s →∞. The main part of this paper gives an analogous result for induced Ramsey numbers: Let be an arbitrary k‐partite k‐uniform hypergraph with classes of size t and an arbitrary k‐graph of order s. We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph such that any red/blue coloring of yields either an induced red copy of or an induced blue copy of ) satisfies . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 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     

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 domination algorithm for {0,1}‐instances of the travelling salesman problem

We present an approximation algorithm for ‐instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial‐time algorithm which has domination ratio . In other words, given a ‐edge‐weighting of the complete graph on vertices, our algorithm outputs a Hamilton cycle of with the following property: the proportion of Hamilton cycles of whose weight is smaller than that of is at most . Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial‐time algorithm with domination ratio for arbitrary edge‐weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant such that cannot be replaced by in the result above. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 427–453, 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     

The threshold for combs in random graphs

For let denote the tree consisting of an ‐vertex path with disjoint ‐vertex paths beginning at each of its vertices. An old conjecture says that for any the threshold for the random graph to contain is at . Here we verify this for with any fixed . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for (with ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 794–802, 2016     

Meyniel's conjecture holds for random graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph , which improves upon existing results showing that asymptotically almost surely the cop number of is provided that for some . We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. This will also be used in a separate paper on random d‐regular graphs, where we show that the conjecture holds asymptotically almost surely when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016     

First passage percolation and escape strategies

Consider first passage percolation on with passage times given by i.i.d. random variables with common distribution F. Let be the time from u to v for a path π and the minimal time among all paths from u to v. We ask whether or not there exist points and a semi‐infinite path such that for all n. Necessary and sufficient conditions on F are given for this to occur. When the support of F is unbounded, we also obtain results on the number of edges with large passage time used by geodesics. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 414–423, 2015     

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     

Universality of random graphs and rainbow embedding

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of . Let the maximum density of a graph H be the maximum average degree of all the subgraphs of H. First, we show that for , a graph w.h.p. contains copies of all spanning graphs H with maximum degree at most Δ and maximum density at most d. For , this improves a result of Dellamonica, Kohayakawa, Rödl and Rucińcki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p. all such graphs for . In particular, if , the random graph therefore contains w.h.p. every spanning tree with maximum degree bounded by Δ. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph H with constant maximum degree, and for suitable p, if we randomly color the edges of a graph with colors, then w.h.p. there exists a rainbow copy of H in G (that is, a copy of H with all edges colored with distinct colors). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 546–564, 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     

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     

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     

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     

A note on the random greedy independent set algorithm

Let r be a fixed constant and let be an r‐uniform, D‐regular hypergraph on N vertices. Assume further that for some . Consider the random greedy algorithm for forming an independent set in . An independent set is chosen at random by iteratively choosing vertices at random to be in the independent set. At each step we chose a vertex uniformly at random from the collection of vertices that could be added to the independent set (i.e. the collection of vertices v with the property that v is not in the current independent set I and contains no edge in ). Note that this process terminates at a maximal subset of vertices with the property that this set contains no edge of ; that is, the process terminates at a maximal independent set. We prove that if satisfies certain degree and codegree conditions then there are vertices in the independent set produced by the random greedy algorithm with high probability. This result generalizes a lower bound on the number of steps in the H‐free process due to Bohman and Keevash and produces objects of interest in additive combinatorics. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 479–502, 2016