Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

Eigenvalues and expansion of bipartite graphs

We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of connected bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes of graphs that are optimal with respect to the bounds. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c, d)-regular bipartite graphs and compare that with with a classical bound.     

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 |.     

Explicit formulas for repeated games with absorbing states

Explicit formulas are given for the asymptotic value lim_{λ → 0} v(λ) and the asymptotic minmax lim w(λ) of finite λ-discounted absorbing games together with new simple proofs for the existence of the limits as λ goes to zero. Similar characterizations for stationary Nash equilibrium payoffs are obtained. The results may be extended to absorbing games with compact metric action sets and jointly-continuous payoff functions.     

Spectral techniques applied to sparse random graphs

We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ₁ ≥ … ≥ λ_n be the eigenvalues of an n‐vertex graph, and let λ = max[λ₂,|λ_n|]. Let c be a large enough constant. For graphs of average degree d = c log n it is well known that λ₁ ≥ d, and we show that . For d = c it is no longer true that , but we show that by removing a small number of vertices of highest degree in G, one gets a graph G′ for which . Our proofs are based on the techniques of Friedman Kahn and Szemeredi from STOC 1989, who proved similar results for regular graphs. Our results are useful for extending the analysis of certain heuristics to sparser instances of NP‐hard problems. We illustrate this by removing some unnecessary logarithmic factors in the density of k‐SAT formulas that are refuted by the algorithm of Goerdt and Krivelevich from STACS 2001. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Phase transition for SIR model with random transition rates on complete graphs

We are concerned with the susceptible-infective-removed (SIR) model with random transition rates on complete graphs C _n with n vertices. We assign independent and identically distributed (i.i.d.) copies of a positive random variable ξ on each vertex as the recovery rates and i.i.d. copies of a positive random variable ρ on each edge as the edge infection weights. We assume that a susceptible vertex is infected by an infective one at rate proportional to the edge weight on the edge connecting these two vertices while an infective vertex becomes removed with rate equals the recovery rate on it, then we show that the model performs the following phase transition when at t = 0 one vertex is infective and others are susceptible. There exists λ _c > 0 such that when λ < λ _c ; the proportion r∞ of vertices which have ever been infective converges to 0 weakly as n → +∞ while when λ > λ _c ; there exist c(λ) > 0 and b(λ) > 0 such that for each n ≥ 1 with probability p ≥ b(λ); the proportion r_∞ ≥ c(λ): Furthermore, we prove that λ _c is the inverse of the production of the mean of ρ and the mean of the inverse of ξ.     

Spin depolarization decay rates in α-symmetric stable fields on cubic lattices

We study the asymptotic, long-time behavior of the energy function where {X_s : 0 ≤ s < ∞} is the standard random walk on the d-dimensional lattice Z^d, 1 < α ≤ 2, and f:R⁺ → R⁺ is any nondecreasing concave function. In the special case f(x) = x, our setting represents a lattice model for the study of transverse magnetization of spins diffusing in a homogeneous, α-stable, i.i.d., random, longitudinal field {λV(x) : x ∈ Z^d} with common marginal distribution, the standard α-symmetric stable distribution; the parameter λ describes the intensity of the field. Using large-deviation techniques, we show that S_c(λ α f) = lim_t→∞ E(t; λ f) exists. Moreover, we obtain a variational formula for this decay rate S_c. Finally, we analyze the behavior S_c(λ α f) as λ → 0 when f(x) = x^β for all 1 ≥ β > 0. Consequently, several physical conjectures with respect to lattice models of transverse magnetization are resolved by setting β = 1 in our results. We show that S_c(λ, α, 1) ≈ λ^α for d ≥ 3, λ^agr;(ln 1/λ)^α−1 in d = 2, and in d = 1. © 1996 John Wiley & Sons, Inc.     

Block designs and graph imbeddings

Heffter first observed that certain imbeddings of complete graphs give rise to BIBD's with k = 3 and λ = 2 (and sometimes λ = 1); Alpert established a one-to-one correspondence between BIBD's with k = 3 and λ = 2 and triangulation systems for complete graphs. In this paper we extend this correspondence to PBIBD's on two association classes with k = 3, λ₁ = 0 and λ₂ = 2, and triangulation systems for strongly regular graphs. The group divisible designs of Hanani are used to construct triangulations for the graphs K_n(m), in each case permitted by the euler formula. Conversely, triangular imbeddings of K_n(m) are constructed which lead to new group divisible designs. A process is developed for “doubling” a given PBIBD of an appropriate form. Various extensions of these ideas are discussed, as is an application to the construction of quasigroups.     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

Triangle-free graphs whose independence number equals the degree

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=α(G) and the fractional chromatic number must satisfy χ_f(G)=|G|/α(G). We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G∈S with χ_f(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.     

Complete bounded λ-hypersurfaces in the weighted volume-preserving mean curvature flow

In this paper, we study the complete bounded λ-hypersurfaces in the weighted volume-preserving mean curvature flow. Firstly, we investigate the volume comparison theorem of complete bounded λ-hypersurfaces with |A|≤α and get some applications of the volume comparison theorem. Secondly, we consider the relation among λ, extrinsic radius k, intrinsic diameter d, and dimension n of the complete λ-hypersurface,and we obtain some estimates for the intrinsic diameter and the extrinsic radius. At last, we get some topological properties of the bounded λ-hypersurface with some natural and general restrictions.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

On the spectral radius of bipartite graphs with given diameter

Let GB(n,d) be the set of bipartite graphs with order n and diameter d. This paper characterizes the extremal graph with the maximal spectral radius in GB(n,d). Furthermore, the maximal spectral radius is a decreasing function on d. At last, bipartite graphs with the second largest spectral radius are determined.     

A Classification of the Strongly Regular Generalised Johnson Graphs

The generalised Johnson graphs are the graphs J(n, k, m) whose vertices are the k subsets of {1, 2, . . . , n}, with two vertices J ₁ and J ₂ joined by an edge if and only if ${{|J_1 \cap J_2| = m}}$ . A graph is called d-regular if every vertex has exactly d edges incident to it. A d-regular graph on v vertices is called a (v, d, a, c)-strongly regular graph if every pair of adjacent vertices have exactly a common neighbours and every pair of non-adjacent vertices have exactly c common neighbours. The triangular graphs J(n, 2, 1), their complements J(n, 2, 0), the sporadic examples J(10, 3, 1) and J(7, 3, 1), as well as the trivially strongly regular graphs J(2k, k, 0) are examples of strongly regular generalised Johnson graphs. In this paper we prove that there are no other strongly regular generalised Johnson graphs.     

A Hard-Core Model on a Cayley Tree: An Example of a Loss Network

The paper is about a nearest-neighbor hard-core model, with fugacity λ>0, on a homogeneous Cayley tree of order k(with k+1 neighbors). This model arises as as a simple example of a loss network with a nearest-neighbor exclusion. We focus on Gibbs measures for the hard core model, in particular on ‘splitting’ Gibbs measures generating a Markov chain along each path on the tree. In this model, ?λ>0 and k≥1, there exists a unique translation-invariant splitting Gibbs measure μ^*. Define λ_c=1/(k?1)×(k/(k?1)) ^k . Then: (i) for λ≤λ_c, the Gibbs measure is unique (and coincides with the above measure μ^*), (ii) for λ>λ_c, in addition to μ^*, there exist two distinct translation-periodic measures, μ₊and μ_?, taken to each other by the unit space shift. Measures μ₊and μ_?are extreme ?λ>λ_c. We also construct a continuum of distinct, extreme, non-translational-invariant, splitting Gibbs measures. For $\lambda >1/(\sqrt k - 1) \times (\sqrt k /\sqrt k - 1))^k $ , measure μ^*is not extreme (this result can be improved). Finally, we consider a model with two fugacities, λ_eand λ_o, for even and odd sites. We discuss open problems and state several related conjectures.     

From regular boundary graphs to antipodal distance-regular graphs

Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ₁ > ··· > λ_d. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ₁, …, λ_d. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998