Independence number,connectivity, and r-factors

We show that if r ? 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ? (r + 1)²/2 and (r + 1)²α(G) ? 4rk(G), then G has an r-factor; if r ? 2 is even and G is a graph with k(G) ? r(r + 2)/2 and (r + 2)α(G) ? 4k(G), then G has an r-factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).     

On hamiltonian-connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |_x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

RESTRICTIONS OF LARGE IRREDUCIBLE REPRESENTATIONS OF THE CLASSICAL GROUPS TO NATURALLY EMBEDDED SMALL SUBGROUPS CANNOT BE SEMISIMPLE

It is proved that the restriction of a p-restricted representation of a classical algebraic group G of rank r in characteristic p > 0 to a naturally embedded semisimple subgroup cannot be completely reducible (semisimple) if the subgroup has a simple component of rank m small enough with respect to r and the highest weight is large enough with respect to p. It suffices to assume that r ≥ 2m and that the highest weight is equal to ∑ ^r _i=1 a_i ω _i with ∑ ^r _i=1 a_i ≥ 2p ? 1 if p ≠ 2 or G ≠ C_r (K) and ∑ ^r _i=1 a_i ≥ 4 for p = 2 and G = C_r (K).     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

On the chromaticity of certain subgraphs of a q-tree

We show that a graph G on n ? q + 1 vertices (where q ? 2) has the chromatic polynomial P(G;λ) = λ(λ ? 1) … (λ ? q + 2) (λ ? q + 1)² (λ ? q)^n?q?1 if and only if G can be obtained from a q-tree Ton n vertices by deleting an edge contained in exactly q ? 1 triangles of T. Furthermore, we prove that these graphs are triangulated.     

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     

A Note on the Embedding of Subspaces of Lp into ℓNr, 0 < r < 1, r ≦ p < 2

In this paper we extend a result by Bourgain-Lindenstrauss-Milman (see [1]). We prove: Let 0 < ? < 1/2, 0< r < 1, r< p < 2. There exists a constant C = C(r,p,?) such that if X is any n-dimensional subspace of L_p(0, l), then there exists Y ? ?^N_r with d(X, Y) ≦ 1 + ?, whenever N > Cn. As an application, we obtain the following partial result: Let 0 < r < 1. There exist constants C = C(r) and C' = C' (r) such that if X is any n-dimensional subspace of L_r(0,1), then there exists Y ? ^N_r with d(X, Y) ≦ C (logn)^l/^r, whenever N ≧ C'n.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

Measure of the multiple self-intersection set of a markov process

Let X(t), t ≧ 0, be a Markov process in R^m with homogeneous transition density p(t; x, y). For a closed bounded set B ? R^m, X is said to have a self-intersection of order r ≧ 2 in B if there are distinct points t₁ < … < t_r such that X(t₁) ∈ B and X(t_j) = X(t¹), for j = 2,…, r. The focus of this work is the Hausdorff measure, suitably defined, of the set of such r-tuples. The main result is that under general conditions on p(t; x, y) as well as the specific condition there is a measure function M(t), defined in terms of the integral above, such that the corresponding Hausdorff measure of self-intersection set is positive, with positive probability. The results are applied to Lévy and diffusion processes, and are shown to extend recent results in this area.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

The multi‐color Ramsey number of an odd cycle

Let r_k(G) be the k‐color Ramsey number of a graph G. It is shown that for k?2 and that r_k(C_{2m+ 1})?(c^kk!)^1/m if the Ramsey graphs of r_k(C_{2m+ 1}) are not far away from being regular. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 324–328, 2009     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

On connectivities of tree graphs

Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.     

Generators of Simple Lie Algebras and the Lower Rank of Some Pro-P Groups

Abstract

Let  be a simple classical Lie algebra over a field F of characteristic p > 7. We show that > d () = 2, where d() is the number of generators of . Let G be a profinite group. We say that G has lower rank ≤ l, if there are {G _α} open subgroups which from a base for the topology at the identity and each G _α is generated (topologically) by no more than l elements. There is a standard way to associate a Lie algebra L(G) to a finitely generated (filtered) pro-p group G. Suppose L(G) ?  ? tF _p [t], where  is a simple Lie algebra over F _p , the field of p elements. We show that the lower rank of G is ≤ d () + 1. We also show that if  is simple classical of rank r and p > 7 or p 2r ² ? r, then the lower rank is actually 2.     

Generalized degree conditions for graphs with bounded independence number

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K_1,m-free grphs we obtain generalizations of known results. In particular we show: Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n ≥ r, n > m) with δ_r(G) ≥ (n/3) + C and β (G) ≥ f(r, m), then (a) G is traceable if δ(G) ≥ r and G is connected; (b) G is hamiltonian if δ(G) ≥ r + 1 and G is 2-connected; (c) G is hamiltonian-connected if δ(G) ≥ r + 2 and G is 3-connected. © 1995 John Wiley & Sons, Inc.     

A shortness exponent for r-regular r-connected graphs

Let r≧ 3 be an integer. It is shown that there exists ε= ε(r), 0 < ε < 1, and an integer N = N(r) > 0 such that for all n ≧ N (if r is even) or for all even n ≧ N(if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than n^ε vertices.     

A remark on divisibility of definable groups

We show that if G is a definably compact, definably connected definable group defined in an arbitrary o‐minimal structure, then G is divisible. Furthermore, if G is defined in an o‐minimal expansion of a field, k ∈ ? and p_k : G → G is the definable map given by p_k (x ) = x^k for all x ∈ G , then we have |(p_k )^–1(x )| ≥ k^r for all x ∈ G , where r > 0 is the maximal dimension of abelian definable subgroups of G . (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Interval Number of a Triangulated Graph

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number ω(G). The following partial results are proved. (1) For each triangulated graph G, i(G) ? ?ω(G)/2? + 1, and this is best possible for 2 ? ω(G) ? 6. (2) For each integer m ? 2, there exists a triangulated graph G with ω(G) = m and i(G) > m^1/2.