σ‐algebras for quasirandom hypergraphs

We examine the correspondence between the various notions of quasirandomness for k‐uniform hypergraphs and σ‐algebras related to measurable hypergraphs. This gives a uniform formulation of most of the notions of quasirandomness for dense hypergraphs which have been studied, with each notion of quasirandomness corresponding to a σ‐algebra defined by a collection of subsets of . We associate each notion of quasirandomness with a collection of hypergraphs, the ‐adapted hypergraphs, so that G is quasirandom exactly when it contains roughly the correct number of copies of each ‐adapted hypergraph. We then identify, for each , a particular ‐adapted hypergraph with the property that if G contains roughly the correct number of copies of then G is quasirandom in the sense of . This generalizes recent results of Kohayakawa, Nagle, Rödl, and Schacht; Conlon, Hàn, Person, and Schacht; and Lenz and Mubayi giving this result for some particular notions of quasirandomness. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 114–139, 2017     

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     

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     

Oscillations in the height of the Yule tree and application to the binary search tree

For a particular case of a branching random walk with lattice support, namely the Yule branching random walk, we prove that the distribution of the centred maximum oscillates around a distribution corresponding to a critical travelling wave in the following sense: there exist continuous functions and such that: where and is the height of the Yule tree. We also shows that similar oscillations occur for , when f is in a large class of functions. This process is classically related to the binary search tree, thus yielding analogous results for the height and for the saturation level of the binary search tree. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 90–120, 2017     

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     

Generalized PageRank on directed configuration networks

This paper studies the distribution of a family of rankings, which includes Google's PageRank, on a directed configuration model. In particular, it is shown that the distribution of the rank of a randomly chosen node in the graph converges in distribution to a finite random variable that can be written as a linear combination of i.i.d. copies of the attracting endogenous solution to a stochastic fixed‐point equation of the form where is a real‐valued vector with , and the are i.i.d. copies of , independent of . Moreover, we provide precise asymptotics for the limit , which when the in‐degree distribution in the directed configuration model has a power law imply a power law distribution for with the same exponent. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 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     

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     

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     

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     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Eigenvalue confinement and spectral gap for random simplicial complexes

We consider the adjacency operator of the Linial‐Meshulam model for random simplicial complexes on n vertices, where each d‐cell is added independently with probability p to the complete ‐skeleton. Under the assumption , we prove that the spectral gap between the smallest eigenvalues and the remaining eigenvalues is with high probability. This estimate follows from a more general result on eigenvalue confinement. In addition, we prove that the global distribution of the eigenvalues is asymptotically given by the semicircle law. The main ingredient of the proof is a Füredi‐Komlós‐type argument for random simplicial complexes, which may be regarded as sparse random matrix models with dependent entries. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 506–537, 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     

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     

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     

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     

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     

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     

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     

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