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     

σ‐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     

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     

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     

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     

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 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     

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     

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     

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     

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     

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     

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     

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     

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     

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     

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     

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     

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