Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

An extension of 0-1 laws

Let σ be a first-order sentence about graphs. For n ? ω let n^α, α ? 0, be the edge probability for the random graph on n vertices, and let pr(σ, n) be the probability that the random graph on n vertices, satisfies σ. If σ and σ satisfy certain conditons then either pr(σ,n)～βn^?γ for some β > 0 and γ ?0, or pr(σ,i)=o(n?γ) for all γ, In particular, this holds for all γ and irrational α. The result has implications for rapidly mixing Markov chains whose stags are finite structures. If the stationary distribution is the same as the for random graphs with edg probability n^?α, then the expected waiting time unitl σ holds (as a function of n) is either bounded above by a polynomial in n, or it grows faster than any polynomical. All these results easily extend to finite structures of any relational type. © 1994 John Wiley & Sons, Inc.     

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 Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

The chromatic number of random Borsuk graphs

We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S^d in , and a pair of vertices is connected if the Euclidean distance between them is at least 2??. We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ?>0 is small and fixed, then the chromatic number is d+2 with high probability. We show that this holds even if ?→0 slowly enough. We quantify the rate at which ? can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ?→0 faster than this, we show that the graph is (d+1)‐colorable with high probability.25     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

Local connectivity of a random graph

A graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +?_n) log n/n)^1/2 where ?_n = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(-exp(-x)).     

The scaling window for a random graph with a given degree sequence

We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( \begin{align*}\mathcal {D}\end{align*}) and prove that if |Q| = O(n^‐1/3R^2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n^2/3R^‐1/3). If |Q| is asymptotically larger than n^‐1/3R^2/3 then the size of the largest component is asymptotically smaller or larger than n^2/3R^‐1/3. Thus, we establish that the scaling window is |Q| = O(n^‐1/3R^2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Random subgraphs of finite graphs: I. The scaling window under the triangle condition

We study random subgraphs of an arbitrary finite connected transitive graph ?? obtained by independently deleting edges with probability 1 ? p. Let V be the number of vertices in ??, and let Ω be their degree. We define the critical threshold p_c = p_c (??, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV^1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p_c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p_c. In particular, we show that the largest cluster inside a scaling window of size |p ? p_c| = Θ(Ω^?1V^?1/3) is of size Θ(V^2/3), while, below this scaling window, it is much smaller, of order O(?^?2 log(V?³)), with ? = Ω(p_c ? p). We also obtain an upper bound O(Ω(p ? p_c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p ? p_c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.     

Counting connected graphs asymptotically

We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

A new approach to the giant component problem

We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence. We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n^?1/3, where ω(n) → ∞ arbitrarily slowly. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

First-order and monadic properties of highly sparse random graphs

A random graph is said to obey the (monadic) zero–one k-law if, for any property expressed by a first-order formula (a second-order monadic formula) with a quantifier depth of at most k, the probability of the graph having this property tends to either zero or one. It is well known that the random graph G(n, n^–α) obeys the (monadic) zero–one k-law for any k ∈ ? and any rational α > 1 other than 1 + 1/m (for any positive integer m). It is also well known that the random graph does not obey both k-laws for the other rational positive α and sufficiently large k. In this paper, we obtain lower and upper bounds on the largest at which both zero–one k-laws hold for α = 1 + 1/m.     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

Countable sparse random graphs

For each irrational a, 0<a<1, a particular countable graph G is defined which mirrors the asymptotic behavior of the random graph G(n, p) with edge probability p = n^?a.     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Space complexity of random formulae in resolution

We study the space complexity of refuting unsatisfiable random k-CNFs in the Resolution proof system. We prove that for Δ ≥ 1 and any ϵ > 0, with high probability a random k-CNF over n variables and Δn clauses requires resolution clause space of Ω(n/Δ^1+ϵ). For constant Δ, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density Δ ≫ n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with Δn clauses requires treelike refutation size of exp(Ω(n/Δ^1+ϵ)), for any ϵ > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92–109, 2003     

On triangle‐free random graphs

We show that for every k≥1 and δ>0 there exists a constant c>0 such that, with probability tending to 1 as n→∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M≥cn^3/2 edges can be made bipartite by deleting ⌊δM⌋ edges. As an immediate consequence of this fact we infer that if M/n^3/2→∞ but M/n²→0, then the probability that a random graph G(n, M) contains no triangles decreases as 2^−(1+o(1))M. We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000