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     

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     

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     

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     

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     

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     

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     

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     

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     

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     

Inside the critical window for cohomology of random k‐complexes

We prove sharper versions of theorems of Linial–Meshulam and Meshulam–Wallach which describe the behavior for ‐cohomology of a random k‐dimensional simplicial complex within a narrow transition window. In particular, we show that if Y is a random k‐dimensional simplicial complex with each k‐simplex appearing i.i.d. with probability with and fixed, then the dimension of cohomology is asymptotically Poisson distributed with mean . In the k = 2 case we also prove that in an accompanying growth process, with high probability, vanishes exactly at the moment when the last ‐simplex gets covered by a k‐simplex, a higher‐dimensional analogue of a “stopping time” theorem about connectivity of random graphs due to Bollobás and Thomason. Random Struct. Alg., 2015 © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 102–124, 2016     

Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori

We show that if , then is ‐close to a junta depending upon at most coordinates, where denotes the edge‐boundary of in the ‐grid. This bound is sharp up to the value of the absolute constant in the exponent. This result can be seen as a generalisation of the Junta theorem for the discrete cube, from [6], or as a characterisation of large subsets of the ‐grid whose edge‐boundary is small. We use it to prove a result on the structure of Lipschitz functions between two discrete tori; this can be seen as a discrete, quantitative analogue of a recent result of Austin [1]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 253–279, 2016     

Testing properties of functions on finite groups

We study testing properties of functions on finite groups. First we consider functions of the form , where G is a finite group. We show that conjugate invariance, homomorphism, and the property of being proportional to an irreducible character is testable with a constant number of queries to f, where a character is a crucial notion in representation theory. Our proof relies on representation theory and harmonic analysis on finite groups. Next we consider functions of the form , where d is a fixed constant and is the family of d by d matrices with each element in . For a function , we show that the unitary isomorphism to g is testable with a constant number of queries to f, where we say that f and g are unitary isomorphic if there exists a unitary matrix U such that for any . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 579–598, 2016     

Generating random graphs in biased Maker‐Breaker games

We present a general approach connecting biased Maker‐Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker‐Breaker games. In particular, we show that for , Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a game on . As another application, we show that for , playing a game on , Maker can build a graph which contains copies of all spanning trees having maximum degree with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 615–634, 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     

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     

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     

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     

Graphical balanced allocations and the (1 + β)‐choice process

Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well‐known that the gap between the load of the most loaded bin and the average is , for large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to independent of m. Consider a constrained setting where not all pairs of bins can be sampled. We are given a graph where each node corresponds to a bin. The process sequentially samples an edge from the graph and places a ball in the lesser loaded of its endpoints. We show the gap is at most where σ is the edge expansion of the graph. Our results extend naturally to the hypergraph version of this question. Our technique involves a tight analysis of what we call the “‐choice” process for some parameter : each ball goes to a random bin with probability and the lesser loaded of two random bins with probability β. For this process we show that the gap is , irrespective of m. Moreover the gap stays at in the weighted case for a large class of weight distributions. No non‐trivial bounds were previously known in the weighted case, even for the 2‐choice case. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 760–775, 2015     

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