Complete solution for the rainbow numbers of matchings

For a given graph H and a positive n, the rainbow number ofH, denoted by rb(n,H), is the minimum integer k so that in any edge-coloring of K_n with k colors there is a copy of H whose edges have distinct colors. In 2004, Schiermeyer determined rb(n,kK₂) for all n≥3k+3. The case for smaller values of n (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible n and hence determine the rainbow number of matchings.     

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.     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

An Anti-Ramsey Theorem on Diamonds

Let G be the diamond (the graph obtained from K ₄ by deleting an edge) and, for every n ≥ 4, let f(n, G) be the minimum integer k such that, for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors. Let ext(n, {C ₃, C ₄}) be the maximum number of edges of a graph on n vertices free of triangles and squares. Here we prove that for every n ≥ 4,

Finding a monochromatic subgraph or a rainbow path

For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of K_N contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = P_k. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,P_k), for k = 4 and 5, equals the (k ? 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory     

The Crossing Number of C(8, 2)□P n

C(n, k) is a graph obtained from n-cycle by adding edges v _i v _i+k (i = 1, 2,...,n, i + k (mod n)). There are several known results on the crossing numbers of the Cartesian products of C(n, k) (n ≤ 7) with paths, cycles and stars. In this paper we extend these results, and show that the crossing number of the Cartesian product of C(8, 2) with P _n is 8n. Yuanqiu Huang: Research supported by NSFC (10771062) and New Century Excellent Talents in University (NCET-07-0276). Jinwang Liu: Research supported by NSFC (10771058) and Hunan NSFC(O6jj20053).     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Optimal strong parity edge-coloring of complete graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. Let p(G) be the least number of colors in an edge-coloring of G having no parity path (a parity edge-coloring). Let (G) be the least number of colors in an edge-coloring of G having no open parity walk (a strong parity edge-coloring). Always (G) ≥ p(G) ≥ χ′(G). We prove that (K _n ) = 2^⌈lgn⌉ − 1 for all n. The optimal strong parity edge-coloring of K _n is unique when n is a power of 2, and the optimal colorings are completely described for all n. Partially supported by NSF grant CCR 0093348. Work supported in part by the NSA under Award No. MDA904-03-1-0037.     

The commutant of analytic Toeplitz operators on Bergman space

In this paper, using the matrix skills and operator theory techniques we characterize the commutant of analytic Toeplitz operators on Bergman space. For f（z） = z^ng（z） （n ≥1）, g（z） = b0 ＋ b1z^p1 ＋b2z^p2 ＋.. , bk ≠ 0 （k = 0, 1, 2,...）, our main result is =A′（Mf） = A′（Mzn）∩A′（Mg） = A′（Mz^s）, where s = g.c.d.（n,p1,p2,...）. In the last section, we study the relation between strongly irreducible curve and the winding number W（f,f（α））, α ∈ D.     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

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

Constrained Ramsey numbers for rainbow matching

The Ramsey number R_k(G) of a graph G is the minimum number N, such that any edge coloring of K_N with k colors contains a monochromatic copy of G. The constrained Ramsey number f(G, T) of the graphs G and T is the minimum number N, such that any edge coloring of K_N with any number of colors contains a monochromatic copy of G or a rainbow copy of T. We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK₂) = R_{t ? 1}(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011     

Multiple vertex coverings by specified induced subgraphs

Given graphs H₁,…, H_k, let f(H₁,…, H_k) be the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove constructively that f(H₁, H₂) ≤ 2(n(H₁) + n(H₂) − 2); equality holds when H₁ = H ₂ = K_n. We prove that f(H₁, K _n) = n + 2√δ(H₁)n + O(1) as n → ∞. We also determine f(K_{1, m −1}, K _n) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000     

Sharp Bounds For Some Multicolor Ramsey Numbers

Let H ₁,H ₂, . . .,H _k+1 be a sequence of k+1 finite, undirected, simple graphs. The (multicolored) Ramsey number r(H ₁,H ₂,...,H _k+1) is the minimum integer r such that in every edge-coloring of the complete graph on r vertices by k+1 colors, there is a monochromatic copy of H _i in color i for some 1ik+1. We describe a general technique that supplies tight lower bounds for several numbers r(H ₁,H ₂,...,H _k+1) when k2, and the last graph H _k+1 is the complete graph K _m on m vertices. This technique enables us to determine the asymptotic behaviour of these numbers, up to a polylogarithmic factor, in various cases. In particular we show that r(K ₃,K ₃,K _m ) = (m ³ poly logm), thus solving (in a strong form) a conjecture of Erdos and Sós raised in 1979. Another special case of our result implies that r(C ₄,C ₄,K _m ) = (m ² poly logm) and that r(C ₄,C ₄,C ₄,K _m ) = (m ²/log² m). The proofs combine combinatorial and probabilistic arguments with spectral techniques and certain estimates of character sums.* Research supported in part by a State of New Jersey grant, by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. Research supported by NSF grant DMS 9704114.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Endomorphisms of superelliptic jacobians

Let K be a field of characteristic zero, n ≥ 5 an integer, f(x) an irreducible polynomial over K of degree n, whose Galois group contains a doubly transitive simple non-abelian group. Let p be an odd prime, the ring of integers in the pth cyclotomic field, C _{f, p} : y ^p  =  f(x) the corresponding superelliptic curve and J(C _{f, p} ) its jacobian. Assuming that either n  =  p + 1 or p does not divide n(n  −  1), we prove that the ring of all endomorphisms of J(C _{f, p} ) coincides with . The same is true if n  =  4, the Galois group of f(x) is the full symmetric group S ₄ and K contains a primitive pth root of unity. An erratum to this article can be found at     

On the solutions of a boundary value problem arising in free convection with prescribed heat flux

For given , c < 0, we are concerned with the solution f _b of the differential equation f ′′′ + ff ′′ + g(f ′) = 0 satisfying the initial conditions f(0) = a, f ′ (0) = b, f ′′ (0) = c, where g is some nonnegative subquadratic locally Lipschitz function. It is proven that there exists b _* > 0 such that f _b exists on [0, + ∞) and is such that as t → + ∞, if and only if b ≥ b _*. This allows to answer questions about existence, uniqueness and boundedness of solutions to a boundary value problem arising in fluid mechanics, and especially in boundary layer theory.      

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

Homology of GL<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>: injectivity conjecture for GL<Subscript>4</Subscript>

The homology of GL _n (R) and SL _n (R) is studied, where R is a commutative ‘ring with many units’. Our main theorem states that the natural map H ₄(GL₃(R), k) → H ₄(GL₄(R), k) is injective, where k is a field with char(k) ≠ 2, 3. For an algebraically closed field F, we prove a better result, namely, is injective. We will prove a similar result replacing GL by SL. This is used to investigate the indecomposable part of the K-group K ₄(R).