The critical behavior of random digraphs

We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε³n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size O_p(|ε|^?1). On the other hand, if ε³n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε²n, whereas all other components are of size O_p(ε^?1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A phase transition phenomenon in a random directed acyclic graph

Let a random directed acyclic graph be defined as being obtained from the random graph G_{n, p} by orienting the edges according to the ordering of vertices. Let γ_n* be the size of the largest (reflexive, transitive) closure of a vertex. For p=c(log n)/n, we prove that, with high probability, γ_n* is asymptotic to n^c log n, 2n(log log n)/log n, and n(1−1/c) depending on whether c<1, c=1, or c>1. We also determine the limiting distribution of the first vertex closure in all three ranges of c. As an application, we show that the expected number of comparable pairs is asymptotic to n^1+c/c log n, ½(n(log log n)/log n)², and ½(n(1−1/c))², respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001     

The cores of random hypergraphs with a given degree sequence

We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d₁…,d_n), maximum degree Δ = o(n^1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n^2/3 Δ^4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The emergence of a giant component in random subgraphs of pseudo‐random graphs

Let G be a d‐regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue λ which is second largest in absolute value satisfies λ = o(d). Let G_p with p = α/d be obtained from G by including each edge of G independently with probability p. We show that if α < 1, then whp the maximum component size of G_p is O(log n) and if α > 1, then G_p contains a unique giant component of size Ω(n), with all other components of size O(log n). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The order of the largest complete minor in a random graph

Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let G_n,p denote a random graph on n vertices with edge probability p. Bollobás, Catlin, and Erd?s (Eur J Combin 1 (1980), 195–199) asymptotically determined ccl(G_n,p) when p is a constant. ?uczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721–748) gave bounds on ccl(G_n,p) when p is very close to 1/n, i.e. inside the phase transition. We show that for every ε > 0 there exists a constant C such that whenever C/n < p < 1 ‐ ε then asymptotically almost surely ccl(G_n,p) = (1 ± ε)n/ , where b := 1/(1 ‐ p). If p = C/n for a constant C > 1, then ccl(G_n,p) = Θ( ). This extends the results in (Bollobás, Catlin, and P. Erd?s, Eur J Combin 1 (1980), 195–199) and answers a question of Krivelevich and Sudakov (preprint, 2006). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

On deviations between empirical and quantile processes for mixing random variables

Let {X_n} be a strictly stationary φ-mixing process with Σ_j=1^∞ φ^1/2(j) < ∞. It is shown in the paper that if X₁ is uniformly distributed on the unit interval, then, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = (O(n^−3/4(log n)^1/2(log log n)^1/4) a.s., where F_n and F_n⁻¹(t) denote the sample distribution function and tth sample quantile, respectively. In case {X_n} is strong mixing with exponentially decaying mixing coefficients, it is shown that, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)^1/2(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)(log log n)^1/4) a.s. The results are further extended to general distributions, including some nonregular cases, when the underlying distribution function is not differentiable. The results for φ-mixing processes give the sharpest possible orders in view of the corresponding results of Kiefer for independent random variables.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Age-dependent branching processes in random environments

We consider an age-dependent branching process in random environments. The environments are represented by a stationary and ergodic sequence ξ = (ξ0,ξ1,...) of random variables. Given an environment ξ, the process is a non-homogenous Galton-Watson process, whose particles in n-th generation have a life length distribution G(ξn) on R , and reproduce independently new particles according to a probability law p(ξn) on N. Let Z(t) be the number of particles alive at time t. We first find a characterization of the conditional probability generating function of Z(t) (given the environment ξ) via a functional equation, and obtain a criterion for almost certain extinction of the process by comparing it with an embedded Galton-Watson process. We then get expressions of the conditional mean EξZ(t) and the global mean EZ(t), and show their exponential growth rates by studying a renewal equation in random environments.     

Uniform bound in the central limit theorem for Banach space valued dependent random variables

Let F be a Banach space with a sufficiently smooth norm. Let (X_i)_i≤n be a sequence in L_F², and T be a Gaussian random variable T which has the same covariance as X = Σ_i≤nX_i. Assume that there exists a constant G such that for s, δ≥0, we have P(sTs+δ)Gδ. (*) We then give explicit bounds of Δ(X) = sup_i|P(|X|≤t)−P(|T|≤t)| in terms of truncated moments of the variables X_i. These bounds hold under rather mild weak dependence conditions of the variables. We also construct a Gaussian random variable that violates (^*).     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The cover time of the giant component of a random graph

We study the cover time of a random walk on the largest component of the random graph G_n,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008