On cliques and bicliques

For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K_m of order m and a biclique K(n, n). We show that g(m, n) = 2(m + n − 2) if m ≤ n − 2. Furthermore, for m ≥ n − 1, we establish that ≡ 0 mod(n − 1) or, if m is sufficiently large and is not an integer. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 60–66, 2000     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000     

A lower bound for the crossing number of Cm × Cn

We prove that the crossing number of C_m × C_n is at least (m − 2)n/3, for all m, n such that n ≥ m. This is the best general lower bound known for the crossing number of C_m × C_n, whose exact value has been long conjectured to be (m − 2)n, for 3 ≤ m ≤ n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 222–226, 2000     

On a Delay Reaction-Diffusion Difference Equation of Neutral Type

In this paper, we first consider a delay difference equation of neutral type of the form: Δ(y _n + py _n−k + q _n y _n−l = 0 for n∈ℤ⁺(0) (1*) and give a different condition from that of Yu and Wang (Funkcial Ekvac, 1994, 37(2): 241–248) to guarantee that every non-oscillatory solution of (1*) with p = 1 tends to zero as n→∞. Moreover, we consider a delay reaction-diffusion difference equation of neutral type of the form: Δ₁(u _n,m + pu _n−k,m ) + q _n,m u _n−l,m = a ²Δ² ₂ u _{n +1, m−1} for (n,m) ∈ℤ⁺ (0) ×Ω, (2*) study various cases of p in the neutral term and obtain that if p≥−1 then every non-oscillatory solution of (2*) tends uniformly in m∈Ω to zero as n→∞; if p = −1 then every solution of (2*) oscillates and if p < −1 then every non-oscillatory solution of (2*) goes uniformly in m∈Ω to infinity or minus infinity as n→∞ under some hypotheses. Received July 14, 1999, Revised August 10, 2000, Accepted September 30, 2000     

Spectral structure of Anderson type Hamiltonians

We study self adjoint operators of the form?H _ω = H ₀ + ∑λ_ω(n) <δ _n ,·>δ _n ,?where the δ _n ’s are a family of orthonormal vectors and the λ_ω(n)’s are independently distributed random variables with absolutely continuous probability distributions. We prove a general structural theorem saying that for each pair (n,m), if the cyclic subspaces corresponding to the vectors δ _n and δ _m are not completely orthogonal, then the restrictions of H _ω to these subspaces are unitarily equivalent (with probability one). This has some consequences for the spectral theory of such operators. In particular, we show that “well behaved” absolutely continuous spectrum of Anderson type Hamiltonians must be pure, and use this to prove the purity of absolutely continuous spectrum in some concrete cases. Oblatum 27-V-1999 & 6-I-2000?Published online: 8 May 2000     

The Ramsey number for a cycle of length five vs. a complete graph of order six

It has been conjectured that r(C_m, K_n) = (m − 1)(n − 1) + 1 for all m ≥ n ≥ 4. This has been proved recently for n = 4 and n = 5. In this paper, we prove that r(C₅, K₆) = 21. This raises the possibility that r(C_m, K₆) = 5m − 4 for all m ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 99–108, 2000     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Martingales in Banach Lattices

In this article, we present a version of martingale theory in terms of Banach lattices. A sequence of contractive positive projections (E_n) on a Banach lattice F is said to be a filtration if E_nE_m = E_{n∧ m}. A sequence (x_n) in F is a martingale if E_nx_m = x_n whenever n ≤ m. Denote by M = M(F, (E_n)) the Banach space of all norm uniformly bounded martingales. It is shown that if F doesn’t contain a copy of c₀ or if every E_n is of finite rank then M is itself a Banach lattice. Convergence of martingales is investigated and a generalization of Doob Convergence Theorem is established. It is proved that under certain conditions one has isometric embeddings . Finally, it is shown that every martingale difference sequence is a monotone basic sequence. Mathematics Subject Classification (2000). 60G48, 46B42     

Convexity preserving and predicting by Bernstein polynomials

It is known that the Bernstein polynomials of a function f defined on [0, 1 ] preserve its convexity properties, i.e., if f⁽ⁿ⁾ 0 then for m n, (B_mf)⁽ⁿ⁾ 0. Moreover, if f is n-convex then (B_mf)⁽ⁿ⁾ 0. While the converse is not true, we show that if f is bounded on (a, b) and if for every subinterval [α, β] (a, b) the nth derivative of the mth Bernstein polynomial of f on [α, β] is nonnegative then f is n-convex.     

Graphs of Non-Crossing Perfect Matchings

 Let P _n be a set of n=2m points that are the vertices of a convex polygon, and let ℳ _m be the graph having as vertices all the perfect matchings in the point set P _n whose edges are straight line segments and do not cross, and edges joining two perfect matchings M ₁ and M ₂ if M ₂=M ₁−(a,b)−(c,d)+(a,d)+(b,c) for some points a,b,c,d of P _n . We prove the following results about ℳ _m : its diameter is m−1; it is bipartite for every m; the connectivity is equal to m−1; it has no Hamilton path for m odd, m>3; and finally it has a Hamilton cycle for every m even, m≥4. Received: October 10, 2000 Final version received: January 17, 2002 RID="*" ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933 Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper.     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.     

On exactlym times covers

In this paper it is shown that if every integer is covered bya ₁+n ₁ℤ,…,a _k +n _k ℤ exactlym times then for eachn=1,…,m there exist at least ( _n ^m ) subsetsI of {1,…k} such that ∑ _{i ∈ I} 1/n _i equalsn. The bound ( _n ^m ) is best possible. Research supported by the National Nature Science Foundation of P.R. of China.     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

Smoothness of convolution powers of orbital measures on the symmetric space SU(n)/SO(n)

We prove that if m_a = m_K*d_a*m_K{\mu _{a}\,{=}\,m_{K}*\delta _{a}*m_{K}} is the K-bi-invariant measure supported on the double coset KaK í SU(n){KaK\subseteq SU(n)} , for K = SO(n), then m_a^k{\mu _{a}^{k}} is absolutely continuous with respect to the Haar measure on SU(n) for all a not in the normalizer of K if and only if k ≥ n. The measure, μ _a , supported on the minimal dimension double coset has the property that m_a^n-1{\mu _{a}^{n-1}} is singular to the Haar measure.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

On the crossing number of cm × cn

We show that the M-crossing number cr_M(C_m × C_n) of C_m × C_n behaves asymptotically according to lim_n→∞ {cr_M(C_m × C_n)/((m − 2)n)} = 1, for each m ≥ 3. This result reinforces the conjecture cr(C_m × C_n) = (m − 2)n if 3 ≤ m ≤ n, which has been proved only for m ≤ 6. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 163–170, 1998     

Linear maps that strongly preserve regular matrices over the Boolean algebra

The set of all m × n Boolean matrices is denoted by $ \mathbb{M} $ \mathbb{M} _m,n . We call a matrix A ∈ $ \mathbb{M} $ \mathbb{M} _m,n regular if there is a matrix G ∈ $ \mathbb{M} $ \mathbb{M} _n,m such that AGA = A. In this paper, we study the problem of characterizing linear operators on $ \mathbb{M} $ \mathbb{M} _m,n that strongly preserve regular matrices. Consequently, we obtain that if min{m, n} ⩽ 2, then all operators on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserve regular matrices, and if min{m, n} ⩾ 3, then an operator T on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserves regular matrices if and only if there are invertible matrices U and V such that T(X) = UXV for all X ε $ \mathbb{M} $ \mathbb{M} _m,n , or m = n and T(X) = UX ^T V for all X ∈ $ \mathbb{M} $ \mathbb{M} _n .     

On the minimum number of edge-disjoint complete m-partite subgraphs into which Kn can be decomposed

Let α_m(n) denote the minimum number of edge-disjoint complete m-partite subgraphs into which K_n can be decomposed. In [2] the author proved that when m ≥ 3, if (i) n ≡ m and n ≡ m (mod m ?1), or (ii) b ∈ [2, m ?1], n ≥ b(m ?1) + m ? (b ?1), and n ≡ b(m ?1) + m ? (b ?1) (mod m? 1), then α_m(n) = ?(n + m ?3)/(m ?1)? (= ?(n ?1)/(m ?1)?), and that for every integer n, if K_n has an edge-disjoint complete m-partite subgraph decomposition, then α_m(n) ≥ ?(n? 1)/(m? 1)?. In this paper we generally discuss the question as to which integers n's satisfy (or do not) α_m(n) = ?(n ?1)/(m ?1)?. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.     

The braid group B4 is linear

We study a linear representation ρ:B _n ? GL _m (Z[q ^±1,t ^±1]) with m=n(n-1)/2. We will show that for n=4, this representation is faithful. We prove a relation with the new Charney length function. We formulate a conjecture implying that ρ is faithful for all n. Oblatum 15-VI-1999 & 24-II-2000?Published online: 18 September 2000