Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Decomposing a graph into expanding subgraphs

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following:

• A classical result of Lipton, Rose and Tarjan from 1979 states that if is a hereditary family of graphs and every graph in has a vertex separator of size , then every graph in has O(n) edges. We construct a hereditary family of graphs with vertex separators of size such that not all graphs in the family have O(n) edges.
• Trevisan and Arora‐Barak‐Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G's edges.
• Sudakov and the second author have recently shown that every graph with average degree d contains an n‐vertex subgraph with average degree at least and vertex expansion . We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1).

The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super‐linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.     

The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any and any family of groups G_k of order n_k for which , a graph with high probability has diameter at most 2 if and with high probability has diameter greater than 2 if . We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erd?s‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014     

Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time

Let be a connected graph with vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an edge‐process (or E‐process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction. For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the E‐process in terms of the edge expansion rate of the graph G, as measured by eigenvalue gap of the transition matrix of a simple random walk on G. A vertex v is ?‐good, if any even degree subgraph containing all edges incident with v contains at least ? vertices. A graph G is ?‐good, if every vertex has the ?‐good property. Let G be an even degree ?‐good expander of bounded maximum degree. Any E‐process on G has vertex cover time This is to be compared with the lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on‐line by an adversary. As no walk based process can cover an n vertex graph in less than n – 1 steps, the cover time of the E‐process is of optimal order when . With high probability random r‐regular graphs, even, have . Thus the vertex cover time of the E‐process on such graphs is . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 36–54, 2015     

The random connection model: Connectivity,edge lengths,and degree distributions

Consider the random graph whose vertex set is a Poisson point process of intensity n on . Any two vertices are connected by an edge with probability , independently of all other edges, and independent of the other points of . d is the toroidal metric, r > 0 and is non‐increasing and . Under suitable conditions on g, almost surely, the critical parameter M_n for which does not have any isolated nodes satisfies . Let , and θ be the volume of the unit ball in . Then for all , is connected with probability approaching one as . The bound can be seen to be tight for the usual random geometric graph obtained by setting . We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy .     

Chromatic thresholds in dense random graphs

The chromatic threshold of a graph H with respect to the random graph G (n, p ) is the infimum over d > 0 such that the following holds with high probability: the family of H‐free graphs with minimum degree has bounded chromatic number. The study of the parameter was initiated in 1973 by Erd?s and Simonovits, and was recently determined for all graphs H . In this paper we show that for all fixed , but that typically if . We also make significant progress towards determining for all graphs H in the range . In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 185–214, 2017     

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     

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     

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     

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     

Finding cycles and trees in sublinear time

We present sublinear‐time (randomized) algorithms for finding simple cycles of length at least and tree‐minors in bounded‐degree graphs. The complexity of these algorithms is related to the distance of the graph from being C_k‐minor free (resp., free from having the corresponding tree‐minor). In particular, if the graph is ‐far from being cycle‐free (i.e., a constant fraction of the edges must be deleted to make the graph cycle‐free), then the algorithm finds a cycle of polylogarithmic length in time , where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of one‐sided error property testing algorithms in the bounded‐degree graphs model. For example, we show that cycle‐freeness of N‐vertex graphs can be tested with one‐sided error within time complexity , where ? denotes the proximity parameter. This matches the known query lower bound for one‐sided error cycle‐freeness testing, and contrasts with the fact that any minor‐free property admits a two‐sided error tester of query complexity that only depends on ?. We show that the same upper bound holds for testing whether the input graph has a simple cycle of length at least k, for any . On the other hand, for any fixed tree T, we show that T‐minor freeness has a one‐sided error tester of query complexity that only depends on the proximity parameter ?. Our algorithm for finding cycles in bounded‐degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree‐minors in complexity. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 139–184, 2014     

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

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

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     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

On the max‐cut of sparse random graphs

We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max‐Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value . It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of .     

High degrees in random recursive trees

For , let T_n be a random recursive tree (RRT) on the vertex set . Let be the degree of vertex v in T_n, that is, the number of children of v in T_n. Devroye and Lu showed that the maximum degree Δ_n of T_n satisfies almost surely; Goh and Schmutz showed distributional convergence of along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in T_n. For any , let . Also, let be a Poisson point process on with rate function . We show that, up to lattice effects, the vectors converge weakly in distribution to . We also prove asymptotic normality of when slowly, and obtain precise asymptotics for when and is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT.     

On MAXCUT in strictly supercritical random graphs,and coloring of random graphs and random tournaments

We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every , there exists such that w.h.p. is not homomorphic to the cycle on vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse edges to make it 2‐colorable.