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     

On the threshold for the Maker‐Breaker H‐game

We study the Maker‐Breaker H‐game played on the edge set of the random graph . In this game two players, Maker and Breaker, alternately claim unclaimed edges of , until all edges are claimed. Maker wins if he claims all edges of a copy of a fixed graph H; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an H‐game is given by the threshold of the corresponding Ramsey property of with respect to the graph H. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 558–578, 2016     

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 .     

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.     

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     

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.     

A threshold for the Maker‐Breaker clique game

We study the Maker‐Breaker k‐clique game played on the edge set of the random graph G(n, p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n, p), until all the edges are claimed. Maker wins if he claims all the edges of a k‐clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at , for all k > 3, thus proving a conjecture from Ref. [Stojakovi? and Szabó, Random Struct Algor 26 (2005), 204–223]. More precisely, we conclude that there exist constants such that when the game is Maker's win a.a.s., and when it is Breaker's win a.a.s. For the triangle game, when k = 3, we give a more precise result, describing the hitting time of Maker's win in the random graph process. We show that, with high probability, Maker can win the triangle game exactly at the time when a copy of K₅ with one edge removed appears in the random graph process. As a consequence, we are able to give an expression for the limiting probability of Maker's win in the triangle game played on the edge set of G(n, p). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 318–341, 2014     

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 .     

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 .     

Line percolation

We study a new geometric bootstrap percolation model, line percolation, on the d‐dimensional integer grid . In line percolation with infection parameter r, infection spreads from a subset of initially infected lattice points as follows: if there exists an axis‐parallel line L with r or more infected lattice points on it, then every lattice point of on L gets infected, and we repeat this until the infection can no longer spread. The elements of the set A are usually chosen independently, with some density p, and the main question is to determine , the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine up to a multiplicative factor of and up to a multiplicative constant as for every fixed . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.     

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.     

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     

Spectra of large diluted but bushy random graphs

We compute an asymptotic expansion in of the limit in of the empirical spectral measure of the adjacency matrix of an Erd?s‐Rényi random graph with vertices and parameter . We present two different methods, one of which is valid for the more general setting of locally tree‐like graphs. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 160–184, 2016     

Intercalates and discrepancy in random Latin squares

An intercalate in a Latin square is a 2 × 2 Latin subsquare. Let be the number of intercalates in a uniformly random n × n Latin square. We prove that asymptotically almost surely , and that (therefore asymptotically almost surely for any ). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in 2 fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low‐discrepancy Latin squares.     

The stripping process can be slow: Part I

Given an integer k, we consider the parallel k‐stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k‐core of H. Take H as : a random r‐uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing with , it has previously been proved that there is a constant such that for all m = cn with constant , with high probability, the parallel k‐stripping process takes iterations. In this paper, we investigate the critical case when . We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches sufficiently fast. A second result we show involves the depth of a non‐k‐core vertex v: the minimum number of steps required to delete v from where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non‐k‐core vertices.     

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.     

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

The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

A set A of non‐negative integers is called a Sidon set if all the sums , with and a₁, , are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of . Results of Chowla, Erd?s, Singer and Turán from the 1940s give that . We study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ by a sparse, random subset R of , and ask how large a subset can be, if we require that S should be a Sidon set. Let be a random subset of of cardinality , with all the subsets of equiprobable. We investigate the random variable , where the maximum is taken over all Sidon subsets , and obtain quite precise information on for the whole range of m, as illustrated by the following abridged version of our results. Let be a fixed constant and suppose . We show that there is a constant such that, almost surely, we have . As it turns out, the function is a continuous, piecewise linear function of a that is non‐differentiable at two ‘critical’ points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function is constant. Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [n]. Our estimates also directly address a problem raised by Cameron and Erd?s (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 1–25, 2015     

Counting dense connected hypergraphs via the probabilistic method

In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.