A spectral heuristic for bisecting random graphs

The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP‐hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs G_n(p,p′) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p′ and edges crossing the partition with probability p independently. If , where c₀ is a suitable constant, then with probability 1 ? o(1) the heuristic finds a minimum bisection of G_n(p,p′) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of G_n(p,p′) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 ? o(1). These results extend previous work of Boppana 5 . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

Randomly coloring graphs with lower bounds on girth and maximum degree

We consider the problem of generating a random q‐coloring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree Δ > c₁ln n and the girth g > c₂ln Δ (n = |V|) for sufficiently large c₁, c₂, then this chain mixes rapidly provided q/Δ > β, where β ≈ 1.763 is the root of β = e^1/β. For this class of graphs, this beats the 11Δ/6 bound of Vigoda 14 for general graphs. We extend the result to random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 167–179, 2003     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Chain Lengths in Certain Random Directed Graphs

We study the random directed graph with vertex set {1, …, n} in which the directed edges (i, j) occur independently with probability c_n/n for i<j and probability zero for i ? j. Let M_n (resp., L_n) denote the length of the longest path (resp., longest path starting from vertex 1). When c_n is bounded away from 0 and ∞ as n→∞, the asymptotic behavior of M_n was analyzed in previous work of the author and J. E. Cohen. Here, all restrictions on c_n are eliminated and the asymptotic behavior of L_n is also obtained. In particular, if c_n/ln(n)→∞ while c_n/n→0, then both M_n/c_n and L_n/c_n are shown to converge in probability to the constant e.     

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     

A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph

We consider non-overlapping subgraphs of fixed order in the random graph K_n, p(n). Fix a strictly strongly balanced graph G. A subgraph of K_{n, p(n)} isomorphic to G is called a G-subgraph. Let X_n be the number of G-subgraphs of K_{n, p(n)} vertex disjoint to all other G-subgraphs. We show that if E[X_n]→∞ as n→, then X_n/E[X_n] converges to 1 in probability. Also, if E[X_n]→c as n→∞, then X_n satisfies a Poisson limit theorem. the Poisson limit theorem is shown using a correlation inequality similar to those appeared in Janson, ?uczak, and Ruciñski[8] and Boppana and Spencer [4].     

On the definability of verbal subgroups

We show that if G is a group of finite Morley rank, then the verbal subgroup <w(G)> is of finite width, where w is a concise word. As a byproduct, we show that if G is any abelian-by-finite group, then G ⁿ =<x ⁿ (G)> is definable. Received: 15 March 1996 / Published online: 18 July 2001     

The sharp threshold for percolation on expander graphs

We consider a random subgraph G _n (p) of a finite graph family G _n = (V _n , E _n ) formed by retaining each edge of G _n independently with probability p. We show that if G _n is an expander graph with vertices of bounded degree, then for any c _n ∈ (0, 1) satisfying $c_n \gg {1 \mathord{\left/ {\vphantom {1 {\sqrt {\ln n} }}} \right. \kern-0em} {\sqrt {\ln n} }}$ and $\mathop {\lim \sup }\limits_{n \to \infty } c_n < 1$ , the property that the random subgraph contains a giant component of order c _n |V _n | has a sharp threshold.     

Toughness and longest cycles in 2-connected planar graphs

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βn^α for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K_2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc.     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

Maximum matchings in sparse random graphs: Karp–Sipser revisited

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G_{n, c/n}, where c>0 is constant. The algorithm was first proposed by Karp and Sipser [Proceedings of the Twenty-Second Annual IEEE Symposium on Foundations of Computing, 1981, pp. 364–375]. We give significantly improved estimates of the errors made by the algorithm. For the subcritical case where c<e we show that the algorithm finds a maximum matching with high probability. If c>e then with high probability the algorithm produces a matching which is within n^1/5+o(1) of maximum size. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 111–177, 1998     

A Bijection for the Alperin Weight Conjecture in <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The Alperin weight conjecture states that if G is a finite group and p is a prime, then the number of irreducible Brauer characters of a group G should be equal to the number of conjugacy classes of p-weights of G. This conjecture is known to be true for the symmetric group S _n , however there is no explicit bijection given between the two sets. In this paper we develop an explicit bijection between the p-weights of S _n and a certain set of partitions that is known to have the same cardinality as the irreducible Brauer characters of S _n . We also develop some properties of this bijection, especially in relation to a certain class of partitions whose corresponding Specht modules over fields of characteristic p are known to be irreducible.     

Rank‐width of random graphs

Rank‐width of a graph G, denoted by rw (G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514–528]. We investigate the asymptotic behavior of rank‐width of a random graph G(n, p). We show that, asymptotically almost surely, (i) if p∈(0, 1) is a constant, then rw (G(n, p)) = ?n/3??O(1), (ii) if , then rw (G(n, p)) = ?1/3??o(n), (iii) if p = c/n and c>1, then rw (G(n, p))?rn for some r = r(c), and (iv) if p?c/n and c81, then rw (G(n, p))?2. As a corollary, we deduce that the tree‐width of G(n, p) is linear in n whenever p = c/n for each c>1, answering a question of Gao [2006]. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Two‐coloring random hypergraphs

A 2‐coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H=H(k, n, p) be a random k‐uniform hypergraph on a vertex set V of cardinality n, where each k‐subset of V is an edge of H with probability p, independently of all other k‐subsets. Let $ m = p{{n}\choose{k}}$ denote the expected number of edges in H. Let us say that a sequence of events ?_n holds with high probability (w.h.p.) if lim_n→∞Pr[?_n]=1. It is easy to show that if m=c2^kn then w.h.p H is not 2‐colorable for c>ln 2/2. We prove that there exists a constant c>0 such that if m=(c2^k/k)n, then w.h.p H is 2‐colorable. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 249–259, 2002     

Supereulerian complementary graphs

Nebeský in [12] show that for any simple graph with n ≥ 5 vertices, either G or G^c contains an eulerian subgraph with order at least n - 1, with an explicitly described class of exceptional graphs. In this note, we show that if G is a simple graph with n ≥ 61 vertices, then either G or G^c is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G^c are connected, then either G or G^c has a 4-flow, or both G and G^c have cut-edges. © 1993 John Wiley & Sons, Inc.     

Analytic proof of the partition identity A 5,3,3(n)=B 5,3,3 0 (n)

In this paper we give an analytic proof of the identity A _5,3,3(n)=B _5,3,3⁰(n), where A _5,3,3(n) counts the number of partitions of n subject to certain restrictions on their parts, and B _5,3,3⁰(n) counts the number of partitions of n subject to certain other restrictions on their parts, both too long to be stated in the abstract. Our proof establishes actually a refinement of that partition identity. The original identity was first discovered by the first author jointly with M. Ruby Salestina and S.R. Sudarshan in [Proceedings of the International Conference on Analytic Number Theory with Special Emphasis on L-functions, Ramanujan Math. Soc., Mysore, 2005, pp. 57–70], where it was also given a combinatorial proof, thus answering a question of Andrews. Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”