Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Tight products and graph expansion

In this article, we study a new product of graphs called tight product. A graph H is said to be a tight product of two (undirected multi) graphs G₁ and G₂, if V(H) = V(G₁) × V(G₂) and both projection maps V(H)→V(G₁) and V(H)→V(G₂) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class‐1 (2k+ 1)‐regular graphs. We also obtain a new model of random d‐regular graphs whose second eigenvalue is almost surely at most O(d^3/4). This construction resembles random graph lifts, but requires fewer random bits. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

Regular graphs of large girth and arbitrary degree

For every integer d≥10, we construct infinite families {G _n } _n∈? of d+1-regular graphs which have a large girth ≥log _d |G _n |, and for d large enough ≥1.33 · log _d |G _n |. These are Cayley graphs on PGL ₂(F _q ) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is a prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families {I _n } _n∈? of d + 1-regular graphs, realized as Cayley graphs on SL ₂(F _q ), and which are displaying a girth ≥0.48·log _d |I _n |. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {M _n } _n∈N of 2 ^k +1-regular graphs were shown to have girth ≥2/3·log₂ ^k |M _n |.     

On the Strong Law of Large Numbers and the Law of the Logarithm for Weighted Sums of Independent Random Variables with Multidimensional Indices

Let (X, X ; ^d} be a field of independent identically distributed real random variables, 0 < p < 2, and {a _, ; ( , ) ^d × ^d, ≤ } a triangular array of real numbers, where ^d is the d-dimensional lattice. Under the minimal condition that sup _, |a _, | < ∞, we show that | |^{− 1/p} ∑ _≤ a _, X → 0 a.s. as | | → ∞ if and only if E(|X|^p(L|X|)^{d − 1}) < ∞ provided d ≥ 2. In the above, if 1 ≤ p < 2, the random variables are needed to be centered at the mean. By establishing a certain law of the logarithm, we show that the Law of the Iterated Logarithm fails for the weighted sums ∑ _≤ a _, X under the conditions that EX = 0, EX² < ∞, and E(X²(L|X|)^{d − 1}/L₂|X|) < ∞ for almost all bounded families {a _, ; ( , ) ^d × ^d, ≤ of numbers.     

Fault Tolerance of Cayley Graphs

It is a difficult problem in general to decide whether a Cayley graph Cay(G; S) is connected where G is an arbitrary finite group and S a subset of G. For example, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. In this paper, it is shown that if a Cayley graph Cay(G; S) is known to be connected then its fault tolerance can be determined in polynomial time in |S|log(|G|). This is accomplished by establishing a new structural result for Cayley graphs. This result also yields a simple proof of optimal fault tolerance for an infinite class of Cayley graphs, namely exchange graphs. We also use the proof technique for our structural result to give a new proof of a known result on quasiminimal graphs. Received March 10, 2006     

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     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

NA随机场对数律的收敛速度

设d是一个正整数, N ^d是d -维正整数格点.设{X_n , n∈N ^d} 是一同分布的负相伴随机场, 记S_n =∑_{k≤ n} X_k, S_n^(k)=S_n-X_k, 如果r >2, EX₁ = 0 和σ²= Var(X₁}, 则存在一个正数M:=100√(r-2)(1+σ²)使得下列条件等价 (I)E |X₁|^r (log|X₁|)^d-1-r/2 <∞; (II)∑_{n∈ N^d} |n|^r/2-2P(max_{1≤ k≤ n} |S_n^(k)|≥ (2^d+1 )ε√|n| log |n |) <∞,∨ε > M; (III)∑_{n∈N ^d} |n|^r/2-2P(max_{1≤ k≤n} |S_k |≥ε√| n} log| n |) <∞,∨ε > M. (III)\ \ $\sum\limits_{{{\bf n}}\in {{\cal N}}^{d}} |n|^{r/2-2} P(\max\limits_{{\bf 1}\leq{\bf k}\leq{\bf n}}|S_{{\bf k}}|\geq \varepsilon \sqrt{|{\bf n}|\log |{\bf n}|})<\infty$, $\forall\varepsilon>M$.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

The acyclic edge chromatic number of a random d‐regular graph is d + 1

We prove the theorem from the title: the acyclic edge chromatic number of a random d‐regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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     

How many elements are needed to generate a finite group with good probability?

We prove that for any real number 0<α<1, there exists a constantc _α such that the probability of generating a finite groupG with [d(G)+c _α log log |G| log log log |G|] elements is at least α.     

Strict Dead-End Elements in Free Soluble Groups

Let G be a group generated by a finite set A. An element g ∈ G is a strict dead end of depth k (with respect to A) if |g|>|ga ₁|>|ga ₁ a ₂|>···>|ga ₁ a ₂… a _k | for any a ₁, a ₂,…, a _k  ∈ A ^±1 such that the word a ₁ a ₂… a _k is freely irreducible. (Here |g| is the distance from g to the identity in the Cayley graph of G.) We show that in finitely generated free soluble groups of degree d ≥ 2 there exist strict dead elements of depth k = k(d), which grows exponentially with respect to d.     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009