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     

On the total variation distance between the binomial random graph and the random intersection graph

When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph and the Erdös‐Rényi graph tends to 0 for any if , where is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any whenever .     

Bounds for pairs in judicious partitioning of graphs

In 2002, Bollobás and Scott posed the following problem: for an integer and a graph G of m edges, what is the smallest f (k, m ) such that V (G ) can be partitioned into V ₁,…,V _k in which for all , where denotes the number of edges with both ends in ? In this paper, we solve this problem asymptotically by showing that . We also show that V (G ) can be partitioned into such that for , where Δ denotes the maximum degree of G . This confirms a conjecture of Bollobás and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017     

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 .     

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.     

The chromatic number of dense random graphs

The chromatic number of a graph G is defined as the minimum number of colors required for a vertex coloring where no two adjacent vertices are colored the same. The chromatic number of the dense random graph where is constant has been intensively studied since the 1970s, and a landmark result by Bollobás in 1987 first established the asymptotic value of . Despite several improvements of this result, the exact value of remains open. In this paper, new upper and lower bounds for are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the coloring rate of to an explicit interval of length o(1), answering a question of Kang and McDiarmid.     

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.     

Chromatic thresholds in sparse 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 was initiated in 1973 by Erd?s and Simonovits. Recently was determined for all graphs H . It is known that for all fixed , but that typically if Here we study the problem for sparse random graphs. We determine for most functions when , and also for all graphs H with © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 215–236, 2017     

A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least infected neighbours becomes infected and remains so forever. Assume that initially vertices are randomly infected, where is the total number of vertices of the graph. Suppose also that , where is the average degree. We determine a critical function such that when , complete infection occurs with high probability as , but when , then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to .     

Extremes of the internal energy of the Potts model on cubic graphs

We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti‐ferromagnetic Potts model on cubic graphs at every temperature and for all . This immediately implies corresponding tight bounds on the anti‐ferromagnetic Potts partition function. Taking the zero‐temperature limit gives new results in extremal combinatorics: the number of q‐colorings of a 3‐regular graph, for any , is maximized by a union of 's. This proves the d = 3 case of a conjecture of Galvin and Tetali.     

Packing perfect matchings in random hypergraphs

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer , the binomial ‐uniform random hypergraph contains edge‐disjoint perfect matchings, provided , where is an integer depending only on . Our result for is asymptotically optimal and for is optimal up to the factor. This significantly improves a result of Frieze and Krivelevich.     

Online purchasing under uncertainty

Suppose there is a collection of independent uniform random variables, and a hypergraph of target structures on the vertex set . We would like to purchase a target structure at small cost, but we do not know all the costs x_i ahead of time. Instead, we inspect the random variables x_i one at a time, and after each inspection, choose to either keep the vertex i at cost x_i, or reject vertex i forever. In the present paper, we consider the case where is the edge‐set of a complete graph (or digraph), and the target structures are the spanning trees of a graph, spanning arborescences of a digraph, the paths between a fixed pair of vertices, perfect matchings, Hamilton cycles or the cliques of some fixed size.     

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     

On replica symmetry of large deviations in random graphs

The following question is due to Chatterjee and Varadhan (2011). Fix and take , the Erd?s‐Rényi random graph with edge density p, conditioned to have at least as many triangles as the typical . Is G close in cut‐distance to a typical ? Via a beautiful new framework for large deviation principles in , Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of where the answer is positive. They further showed that for any small enough p there are at least two phase transitions as r varies. We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed d‐regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all such that lies on the convex minorant of where is the rate function of a binomial with parameter p. In particular, the answer for triangles involves rather than the natural guess of where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of is conditioned to exceed the typical value of the largest eigenvalue of . Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 109–146, 2015     

Interpolating between random walk and rotor walk

We introduce a family of stochastic processes on the integers, depending on a parameter and interpolating between the deterministic rotor walk () and the simple random walk (). This p‐rotor walk is not a Markov chain but it has a local Markov property: for each the sequence of successive exits from is a Markov chain. The main result of this paper identifies the scaling limit of the p‐rotor walk with two‐sided i.i.d. initial rotors. The limiting process takes the form , where is a doubly perturbed Brownian motion, that is, it satisfies the implicit equation (1) for all . Here is a standard Brownian motion and are constants depending on the marginals of the initial rotors on and respectively. Chaumont and Doney have shown that Equation 1 has a pathwise unique solution , and that the solution is almost surely continuous and adapted to the natural filtration of the Brownian motion. Moreover, and . This last result, together with the main result of this paper, implies that the p‐rotor walk is recurrent for any two‐sided i.i.d. initial rotors and any .     

Efficient algorithms for discrepancy minimization in convex sets

A result of Spencer states that every collection of n sets over a universe of size n has a coloring of the ground set with of discrepancy . A geometric generalization of this result was given by Gluskin (see also Giannopoulos) who showed that every symmetric convex body with Gaussian measure at least , for a small , contains a point where a constant fraction of coordinates of y are in . This is often called a partial coloring result. While the proofs of both these results were inherently non‐algorithmic, recently Bansal (see also Lovett‐Meka) gave a polynomial time algorithm for Spencer's setting and Rothvoß gave a randomized polynomial time algorithm obtaining the same guarantee as the result of Gluskin and Giannopoulos. This paper contains several related results which combine techniques from convex geometry to analyze simple and efficient algorithms for discrepancy minimization. First, we prove another constructive version of the result of Gluskin and Giannopoulos, in which the coloring is attained via the optimization of a linear function. This implies a linear programming based algorithm for combinatorial discrepancy obtaining the same result as Spencer. Our second result suggests a new approach to obtain partial colorings, which is also valid for the non‐symmetric case. It shows that every (possibly non‐symmetric) convex body , with Gaussian measure at least , for a small , contains a point where a constant fraction of coordinates of y are in . Finally, we give a simple proof that shows that for any there exists a constant c > 0 such that given a body K with , a uniformly random x from is in cK with constant probability. This gives an algorithmic version of a special case of the result of Banaszczyk.     

Arboricity and spanning‐tree packing in random graphs

We study the arboricity and the maximum number of edge‐disjoint spanning trees of the classical random graph . For all , we show that, with high probability, is precisely the minimum of and , where is the minimum degree of the graph and denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for such that the following holds. Above this threshold, equals and equals . Below this threshold, equals , and we give a two‐value concentration result for the arboricity in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most in the two‐choice load balancing problem, where .     

On the variational problem for upper tails in sparse random graphs

What is the probability that the number of triangles in , the Erd?s‐Rényi random graph with edge density p , is at least twice its mean? Writing it as , already the order of the rate function r (n, p ) was a longstanding open problem when p = o (1), finally settled in 2012 by Chatterjee and by DeMarco and Kahn, who independently showed that for ; the exact asymptotics of r (n, p ) remained unknown. The following variational problem can be related to this large deviation question at : for δ > 0 fixed, what is the minimum asymptotic p‐relative entropy of a weighted graph on n vertices with triangle density at least (1 + δ )p ³? A beautiful large deviation framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles to a limiting version of this problem for fixed p . A very recent breakthrough of Chatterjee and Dembo extended its validity to for an explicit α > 0, and plausibly it holds in all of the above sparse regime. In this note we show that the solution to the variational problem is when vs. when (the transition between these regimes is expressed in the count of triangles minus an edge in the minimizer). From the results of Chatterjee and Dembo, this shows for instance that the probability that for has twice as many triangles as its expectation is where . Our results further extend to k‐cliques for any fixed k , as well as give the order of the upper tail rate function for an arbitrary fixed subgraph when . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 420–436, 2017     

Finding paths in sparse random graphs requires many queries

We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph in order to find a subgraph which possesses some target property with high probability. In this paper we focus on finding long paths in when for some fixed constant . This random graph is known to have typically linearly long paths. To have edges with high probability in one clearly needs to query at least pairs of vertices. Can we find a path of length economically, i.e., by querying roughly that many pairs? We argue that this is not possible and one needs to query significantly more pairs. We prove that any randomised algorithm which finds a path of length with at least constant probability in with must query at least pairs of vertices. This is tight up to the factor. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 71–85, 2017