The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

The length of random subsets of Boolean lattices

We form the random poset 𝒫(n, p) by including each subset of [n]={1,…,n} with probability p and ordering the subsets by inclusion. We investigate the length of the longest chain contained in 𝒫(n, p). For p≥e/n we obtain the limit distribution of this random variable. For smaller p we give thresholds for the existence of chains which imply that almost surely the length of 𝒫(n, p) is asymptotically n(log n−log log 1/p)/log 1/p. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 177–194, 2000     

Approximate counting via random optimization

Let ℱ_n be a family of subsets of {1,…,n}. We propose a simple randomized algorithm to estimate the cardinality of ℱ_n from the maximum weight of a subset X∈ℱ_n in a random weighting of {1,…,n}. The examples include enumeration of perfect matchings in graphs, bases in matroids, and Hamiltonian cycles in graphs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 187–198 (1997)     

Addendum to ‘avoiding a giant component’

We take this opportunity, which is kindly provided by the editors, to add a theorem and to correct the proof of one of the lemmas in the article ‘Avoiding a Giant Component’ [Bohman and Frieze, Avoiding a giant component, Random Struct Alg 19 (2001), 75–85]. The subject of the said article is the following guided random process. Let e₁, $e^{\prime}_{1}$; e₂, $e^{\prime}_{2}$;…;e_i, $e^{\prime}_{i}$;… be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K_n. This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from e_i, $e_{i}^{\prime}$ to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. In Bohman and Frieze [Avoiding a giant component, Random Struct Alg 19 (2001), 75–85], we proved that these choices can be made so that whp (A sequence of events ?_n is said to occur with high probability (whp) if lim_n→∞ Pr (?_n)=1.), the size of the largest component of the graph formed at stage. 535n, is polylogarithmic in n. Here, we make a correction to that proof and prove that the graph formed at stage cn for any constant c>1 will contain a component of size Ω(n) (regardless of how the edges are chosen at each stage). © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 126–130, 2002     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

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     

A sharp inverse Littlewood‐Offord theorem

Let η_i,i = 1,…,n be iid Bernoulli random variables. Given a multiset v of n numbers v₁,…,v_n, the concentration probability P ₁( v ) of v is defined as P ₁( v ) := sup_x P (v₁η₁+ …v_nη_n = x). A classical result of Littlewood–Offord and Erd?s from the 1940s asserts that if the v_i are nonzero, then this probability is at most O(n^‐1/2). Since then, many researchers obtained better bounds by assuming various restrictions on v . In this article, we give an asymptotically optimal characterization for all multisets v having large concentration probability. This allow us to strengthen or recover several previous results in a straightforward manner. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Conditional negative association for competing urns

We prove conditional negative association for random variables x _j = 1 (j∈[n]:= {1…n}) , where σ(1)…σ(m) are i.i.d. from [n]. (The σ(i) 's are thought of as the locations of balls dropped independently into urns 1…n according to some common distribution, so that, for some threshold t_j, x _j is the indicator of the event that at least t_j balls land in urn j.) We mostly deal with the more general situation in which the σ(i) 's need not be identically distributed, proving results which imply conditional negative association in the i.i.d. case. Some of the results—particularly Lemma 8 on graph orientations—are thought to be of independent interest. We also give a counterexample to a negative correlation conjecture of D. Welsh, a strong version of a (still open) conjecture of G. Farr. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph

It is well known [9] that finding a maximal independent set in a graph is in class NC and [10] that finding a maximal independent set in a hypergraph with fixed dimension is in RNC. It is not known whether this latter problem remains in NC when the dimension is part of the input. We will study the problem when the problem instances are randomly chosen. It was shown in [6] that the expected running time of a simple parallel algorithm for finding the lexicographically first maximal independent set (Ifmis) in a random simple graph is logarithmic in the input size. In this paper, we will prove a generalization of this result. We show that if a random k-uniform hypergraph has vertex set {1, 2, …, n} and its edges are chosen independently with probability p from the set of (ⁿ_k) possible edges, then our algorithm finds the Ifmis in O( ) expected time. The hidden constant is independent of k, p. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 359–377 (1996)     

Fibonacci solitaire

Fibonacci Solitaire is a combinatorial algorithm which associates with a permutation of [n]={1,…,n} a partition of [n] into couples and singletons. We study the output configuration when the algorithm is applied to a random permutation, with emphasis on the large n‐asymptotics. We show that the set of singletons, properly scaled, resembles a familiar ‘stick‐breaking’ Poisson configuration, whereas the configuration of couples becomes close to uniform. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 71–88, 2002     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Random intersection graphs when m=ω(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models

When the random intersection graph G(n, m, p) proposed by Karoński, Scheinerman, and Singer‐Cohen [Combin Probab Comput 8 (1999), 131–159] is compared with the independent‐edge G(n, p), the evolutions are different under some values of m and equivalent under others. In particular, when m=n^α and α>6, the total variation distance between the graph random variables has limit 0. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 156–176, 2000     

The action of a few permutations on r-tuples is quickly transitive

We prove that for every r and d≥2 there is a C such that for most choices of d permutations π₁, π₂,…,π_d of S_n, the following holds: for any two r-tuples of distinct elements in {1,…,n}, there is a product of less than C log n of the π_is which map the first r-tuple to the second. Although we came across this problem while studying a rather unrelated cryptographic problem, it belongs to a general context of which random Cayley graph quotients of S_n are good expanders. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 335–350, 1998     

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     

Avoiding a giant component

Let e₁, e′₁; e₂, e′₂;…;e_i, e′_i;??? be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K_n (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from e_i,e′_i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535n is polylogarithmic in n. This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001     

Packing tight Hamilton cycles in 3‐uniform hypergraphs

Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v₁,…,v_n such that every triple of consecutive vertices {v_i,v_i+1,v_i+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Asymptotic behavior of random heaps

We consider a random walk W_n on the locally free group (or equivalently a signed random heap) with m generators subject to periodic boundary conditions. Let #T(W_n) denote the number of removable elements, which determines the heap's growth rate. We prove that lim_n→∞??(#T(W_n))/m ≤ 0.32893 for m ≥ 4. This result disproves a conjecture (due to Vershik, Nechaev and Bikbov [Comm Math Phys 212 (2000), 469–501]) that the limit tends to 1/3 as m → ∞. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

The random binary growth model

We describe a family of models of random partial orders, called classical sequential growth models, and study a specific case, which is the simplest interesting model, called a random binary growth model. This model produces a random poset, called a random binary order, B₂, on the vertex set ? by considering each vertex n ≥ 2 in turn and placing it above 2 vertices chosen uniformly at random from the set {0,…,n ? 1} (with additional relations added to ensure transitivity). We show that B₂ has infinite dimension, almost surely. Using the differential equation method of Wormald, we can closely approximate the size of the up‐set of an arbitrary vertex. We give an upper bound on the largest vertex incomparable with vertex n, which is polynomial in n, and, using this bound, we provide an example of a poset P, such that there is a positive probability that B₂ does not contain P. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

MODp‐tests,almost independence and small probability spaces

In this paper, we consider approximations to probability distributions over Z . We present an approach to estimate the quality of approximations to probability distributions towards the construction of small probability spaces. These small spaces are used to derandomize algorithms. In contrast to results by Even, Goldreich, Luby, Nisan, and Veličković [EGLNV], the methods which are used here are simple, and we get smaller sample spaces. Our investigations are motivated by recent work of Azar, Motwani, and Naor [AMN]. They considered the problem to construct in time respective space polynomial in n a good approximation to the joint probability distribution of the mutually independent random variables X₁, X₂,…,X_n. Each X_i has values in {0, 1} and satisfies X_i=0 with probability q and X_i=1 with probability 1−q where q∈[0, 1] is arbitrary. Our considerations improve on results in [EGLNV] and [AMN] for q=1/p and p a prime. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 293–313, 2000     

The diameter of sparse random graphs

We derive an expression of the form c ln n + o(ln n) for the diameter of a sparse random graph with a specified degree sequence. The result holds asymptotically almost surely, assuming that certain convergence and supercriticality conditions are met, and is applicable to the classical random graph G_n,p with np = Θ(1) + 1, as well as certain random power law graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007