Firefighting on a random geometric graph

LetG_λ be the graph whose vertices are points of a planar Poisson process of density λ, with vertices adjacent if they are within distance 1. A “fire” begins at some vertex and spreads to all neighbors in discrete steps; in the meantime f vertices can be deleted at each time‐step. Let f_λ be the least f such that, with probability 1, any fire on G_λ can be stopped in finite time. We show that f_λ is bounded between two linear functions of λ. The lower bound makes use of a new result concerning oriented percolation in the plane; the constant factor in the upper bound is is tight, provided a certain conjecture, for which we offer supporting evidence, is correct. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 466–477, 2015     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

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     

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 .     

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     

A random CLT for dependent random variables

We introduce a new condition for {Y_τn} to have the same asymptotic distribution that {Y_n} has, where {Y_n} is a sequence of random elements of a metric space (S, d) and {τ_n} is a sequence of random indices. The condition on {Y_n} is that max_iDnd(Y_i, Y_an)→^p0 as n → ∞, where D_n = {i: |k_i−k_an| ≤ δ_ank_an} and {δ_n} is a nonincreasing sequence of positive numbers. The condition on {τ_n} is that P(|(k_τn/k_an)−1| > δ_an) → 0 as n → ∞. Under these conditions, we will show that d(Y_τn, Y_an) → ^P0 and apply this result to the CLT for a general class of sequences of dependent random variables.     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

The mixing time of the giant component of a random graph

We show that the total variation mixing time of the simple random walk on the giant component of supercritical and is . This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are “decorated expanders” — an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 383–407, 2014     

Degree distribution of a typical vertex in a general random intersection graph

For a general random intersection graph, we show an approximation of the vertex degree distribution by a Poisson mixture. Research supported by Lithuanian State Science and Studies Foundation Grant T-07149.     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

SIR epidemics on random graphs with a fixed degree sequence

Let Δ > 1 be a fixed positive integer. For \begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} let G_z be chosen uniformly at random from the collection of graphs on ∥z∥₁n vertices that have z_in vertices of degree i for i = 1,…,Δ. We determine the likely evolution in continuous time of the SIR model for the spread of an infectious disease on G_z, starting from a single infected node. Either the disease halts after infecting only a small number of nodes, or an epidemic spreads to infect a linear number of nodes. Conditioning on the event that more than a small number of nodes are infected, the epidemic is likely to follow a trajectory given by the solution of an associated system of ordinary differential equations. These results also give the likely number of nodes infected during the course of the epidemic and the likely length in time of the epidemic. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The evolution of the min-min random graph process

We study the following min-min random graph process G=(G₀,G₁,…): the initial state G₀ is an empty graph on n vertices (n even). Further, G_M+1 is obtained from G_M by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in G_M and adding the edge {v,w}. The process may produce multiple edges. We show that G_M is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that G_M is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of G_M for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n⁻¹ln⁴n≤t=o(1) we show that tX converges to a gamma distribution.     

Saturation in random graphs

A graph H is K_s ‐saturated if it is a maximal K_s ‐free graph, i.e., H contains no clique on s vertices, but the addition of any missing edge creates one. The minimum number of edges in a K_s ‐saturated graph was determined over 50 years ago by Zykov and independently by Erd?s, Hajnal and Moon. In this paper, we study the random analog of this problem: minimizing the number of edges in a maximal K_s ‐free subgraph of the Erd?s‐Rényi random graph G (n, p ). We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Our results reveal some surprising behavior of these parameters. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 169–181, 2017     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

Semi‐random graph process

We introduce and study a novel semi‐random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties , we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies . Along the way, we show that the process is general enough to approximate (using suitable strategies) several well‐studied random graph models.     

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