The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Unexpected behaviour of crossing sequences

The nth crossing number of a graph G, denoted ncr(G), is the minimum number of crossings in a drawing of G on an orientable surface of genus n. We prove that for every a>b>0, there exists a graph G for which ₀cr(G)=a, ₁cr(G)=b, and ₂cr(G)=0. This provides support for a conjecture of Archdeacon et al. and resolves a problem of Salazar.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

On aschbacher’s localC(G; T) theorem

Aschbacher’s localC(G; T) theorem asserts that ifG is a finite group withF*(G)=O ₂(G), andTεSyl₂(G), thenG=C(G; T)K(G), whereC(G; T)=〈N _G (T ₀)|1≠T ₀ charT〉 andK(G) is the product of all near components ofG of typeL ₂(2 ⁿ ) orA ₂ ⁿ ₊₁. Near components are also known asχ-blocks or Aschbacher blocks. In this paper we give a proof of Aschbacher’s theorem in the case thatG is aK-group, i.e., in the case that every simple section ofG is isomorphic to one of the known simple groups. Our proof relies on a result of Meierfrankenfeld and Stroth [MS] on quadratic four-groups and on the Baumann-Glauberman-Niles theorem, for which Stellmacher [St2] has given an amalgam-theoretic proof. Apart from those results, our proof is essentially self-contained. For John Thompson Supported in part by NSF grant #DMS 89-03124, by DIMACS, an NSF Science and Technology Center, funded under contract STC-88-09648, and by NSA grant #MDA-904-91-H-0043. Prof. Gorenstein died on August 26, 1992.     

A Property About Minimum Edge- and Minimum Clique-Cover of a Graph

 Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ ⁿ :Ex≤1,x≥0}, P(C)={x∈ℜ ⁿ :Cx≤1,x≥0}, α _E (G)=max{1 ^T x subject to x∈P(E)}, and α _C (G)= max{1 ^T x subject to x∈P(C)}. In this paper we prove that if α _E (G)=α _C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

Triangle-free distance-regular graphs

Let Γ denote a distance-regular graph with diameter d≥3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that ∂(x,y)=∂(z,w)=1, ∂(x,z)=3, and ∂(x,w)=∂(y,w)=∂(y,z)=2, where ∂ denotes the path-length distance function. Assume that Γ has intersection numbers a ₁=0 and a ₂≠0. We prove that the following (i) and (ii) are equivalent. (i) Γ is Q-polynomial and contains no parallelograms of length 3; (ii) Γ has classical parameters (d,b,α,β) with b<−1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)²(b+2)/c ₂, (b−2)(b−1)b(b+1)/(2+2b−c ₂) is an integer and that c ₂≤b(b+1). This upper bound for c ₂ is optimal, since the Hermitian forms graph Her₂(d) is a triangle-free distance-regular graph that satisfies c ₂=b(b+1). Work partially supported by the National Science Council of Taiwan, R.O.C.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

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     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

An inequality for Tutte polynomials

Let G be a graph without loops or bridges and a, b be positive real numbers with b ≥ a(a+2). We show that the Tutte polynomial of G satisfies the inequality T _G (b, 0)T _G (0, b) ≥ T _G (a, a)². Our result was inspired by a conjecture of Merino and Welsh that T _G (1, 1) ≤ max{T _G (2, 0),T _G (0, 2)}.     

Properties of random walks on discrete groups: Time regularity and off-diagonal estimates

In this paper we study some properties of the convolution powers K(n)=K∗K∗?∗K of a probability density K on a discrete group G, where K is not assumed to be symmetric. If K is centered, we show that the Markov operator T associated with K is analytic in Lp(G) for 1<p<∞, and prove Davies-Gaffney estimates in L² for the iterated operators Tn. This enables us to obtain Gaussian upper bounds for the convolution powers K(n). In case the group G is amenable, we discover that the analyticity and Davies-Gaffney estimates hold if and only if K is centered. We also estimate time and space differences, and use these to obtain a new proof of the Gaussian estimates with precise time decay in case G has polynomial volume growth.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

The size-Ramsey number of trees

IfG andH are graphs, let us writeG→(H)₂ ifG contains a monochromatic copy ofH in any 2-colouring of the edges ofG. Thesize-Ramsey number r _e(H) of a graphH is the smallest possible number of edges a graphG may have ifG→(H)₂. SupposeT is a tree of order |T|≥2, and lett ₀,t ₁ be the cardinalities of the vertex classes ofT as a bipartite graph, and let Δ(T) be the maximal degree ofT. Moreover, let Δ₀, Δ₁ be the maxima of the degrees of the vertices in the respective vertex classes, and letβ(T)=T ₀Δ₀+t ₁Δ₁. Beck [7] proved thatβ(T)/4≤r _e(T)=O{β(T)(log|T|)¹²}, improving on a previous result of his [6] stating thatr _e(T)≤Δ(T)|T|(log|T|)¹². In [6], Beck conjectures thatr _e(T)=O{Δ(T)|T|}, and in [7] he puts forward the stronger conjecture thatr _e(T)=O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing thatr _e(T)=O{β(T)logΔ(T)}.     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

Connectivity,graph minors,and subgraph multiplicity

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) times as a subgraph of the K_b,c-free graphs, b ≥ c and c ≤ 4, iff G is c-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Centerpole sets for colorings of abelian groups

A subset C?G of a group G is called k-centerpole if for each k-coloring of G there is an infinite monochromatic subset G, which is symmetric with respect to a point c??C in the sense that S=cS ^?1 c. By c _k (G) we denote the smallest cardinality c _k (G) of a k-centerpole subset in G. We prove that c _k (G)=c _k (? ^m ) if G is an abelian group of free rank m??k. Also we prove that c ₁(? ⁿ⁺¹)=1, c ₂(? ⁿ⁺²)=3, c ₃(? ⁿ⁺³)=6, 8??c ₄(? ⁿ⁺⁴)??c ₄(?⁴)=12 for all n????, and ${\frac{1}{2}(k^{2}+3k-4)\le c_{k}(\mathbb{Z}^{n})\le2^{k}-1-\max_{s\le k-2}\binom {k-1}{s-1}}$ for all n??k??4.