The Bohman‐Frieze process near criticality

The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c ? ? (that is, when the number of edges are (t_c ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?^‐2log n). Further, at t_c + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?^‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Orthogonal Polarity Graphs and Sidon Sets

Determining the maximum number of edges in an n‐vertex C₄‐free graph is a well‐studied problem that dates back to a paper of Erd?s from 1938. One of the most important families of C₄‐free graphs are the Erd?s‐Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose‐Chowla Sidon set is isomorphic to a large induced subgraph of the Erd?s‐Rényi orthogonal polarity graph. Using this isomorphism, we prove that the Petersen graph is a subgraph of every sufficiently large Erd?s‐Rényi orthogonal polarity graph.     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

On a random graph with immigrating vertices: Emergence of the giant component

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O(n^2/3) vertices is shown to be the same as in the Erdős–Rényi graph process with the number of vertices fixed at n at the start. A major difference is that now the transition occurs about a time t=π/2, rather than t=1. The proof has three ingredients. The size of the largest component in the subcritical phase is bounded by comparison with a certain multitype branching process. With this bound at hand, the growth of the sum‐of‐squares and sum‐of‐cubes of component sizes is shown, via martingale methods, to follow closely a solution of the Smoluchowsky‐type equations. The approximation allows us to apply results of Aldous [Brownian excursions, critical random graphs and the multiplicative coalescent, Ann Probab 25 (1997), 812–854] on emergence of giant components in the multiplicative coalescent, i.e., a nonuniform random graph process. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 79–102, 2000     

The evolution of subcritical Achlioptas processes

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. AlthouSgh the evolution of such ‘local’ modifications of the Erd?s–Rényi random graph process has received considerable attention during the last decade, so far only rather simple rules are well understood. Indeed, the main focus has been on ‘bounded‐size’ rules, where all component sizes larger than some constant B are treated the same way, and for more complex rules very few rigorous results are known. In this paper we study Achlioptas processes given by (unbounded) size rules such as the sum and product rules. Using a variant of the neighbourhood exploration process and branching process arguments, we show that certain key statistics are tightly concentrated at least until the susceptibility (the expected size of the component containing a randomly chosen vertex) diverges. Our convergence result is most likely best possible for certain generalized Achlioptas processes: in the later evolution the number of vertices in small components may not be concentrated. Furthermore, we believe that for a large class of rules the critical time where the susceptibility ‘blows up’ coincides with the percolation threshold. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 174–203, 2015     

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     

Bootstrap percolation with inhibition

We study a variant of the classical bootstrap percolation process on Erd?s Rényi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.     

The rank of random graphs

We show that almost surely the rank of the adjacency matrix of the Erd?s‐Rényi random graph G(n,p) equals the number of nonisolated vertices for any c ln n/n ≤ p ≤ 1/2, where c is an arbitrary positive constant larger than 1/2. In particular, the adjacency matrix of the giant component (a.s.) has full rank in this range. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Sparse random graphs: Eigenvalues and eigenvectors

In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph G_n,d in the case d →∞, complementing a previous result of McKay for fixed d. We also obtain a upper bound on the infinity norm of eigenvectors of Erd?s–Rényi random graph G(n,p), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On the vanishing of homology in random Čech complexes

We compute the homology of random ?ech complexes over a homogeneous Poisson process on the d‐dimensional torus, and show that there are, coarsely, two phase transitions. The first transition is analogous to the Erd?s ‐Rényi phase transition, where the ?ech complex becomes connected. The second transition is where all the other homology groups are computed correctly (almost simultaneously). Our calculations also suggest a finer measurement of scales, where there is a further refinement to this picture and separation between different homology groups. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 14–51, 2017     

Upper tails for triangles

With ξ the number of triangles in the usual (Erd?s‐Rényi) random graph G(m,p), p > 1/m and η > 0, we show (for some C_η > 0) This is tight up to the value of C_η. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 452–459, 2012     

Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counter‐intuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erd?s‐Rényi random graphs G (n, p ) with constant edge density , the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of G (n, p ), which might be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 584–611, 2017     

Limiting shape of the depth first search tree in an Erdős‐Rényi graph

We show that the profile of the tree constructed by the depth first search algorithm in the giant component of an Erd?s‐Rényi graph with N vertices and connection probability c/N with c > 1 converges to an explicit deterministic shape. This makes it possible to exhibit a long nonintersecting path of length , where ρ_c is the density of the giant component and Li₂ denotes the dilogarithm function.     

The missing log in large deviations for triangle counts

This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erd?s‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

Cliques in dense inhomogeneous random graphs

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant of the Erd?s–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of for each fixed n , and give examples of graphons for which exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016 © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017     

How big are the increments of G-Brownian motion?

In this paper,we investigate the problem:How big are the increments of G-Brownian motion.We obtain the Csrg and R′ev′esz’s type theorem for the increments of G-Brownian motion.As applications of this result,we get the law of iterated logarithm and the Erds and R′enyi law of large numbers for G-Brownian motion.Furthermore,it turns out that our theorems are natural extensions of the classical results obtained by Csrg and R′ev′esz(1979).     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.