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

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.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

On Sums of Two Coprime k-th Powers(II)

For fixed k ≥ 3, let E_k(x) denote the error term of the sum ?_{n ￡ x}r_k(n)\sum_{n\le x}\rho_k(n) , where r_k(n) = ?_{n=|m|^k+|l|^k, g.c.d.(m,l)=1}\rho_k(n) = \sum_{n=|m|^k+|l|^k, g.c.d.(m,l)=1} 1. It is proved that if the Riemann hypothesis is true, then E₃(x) << x^331/1254+eE_3(x)\ll x^{331/1254+\varepsilon} , E₄(x) << x^37/184+eE_4(x)\ll x^{37/184+\varepsilon} . A short interval result is also obtained.     

Circuits Through Cocircuits In A Graph With Extensions To Matroids

We show that for any k-connected graph having cocircumference c*, there is a cycle which intersects every cocycle of size c*-k + 2 or greater. We use this to show that in a 2-connected graph, there is a family of at most c* cycles for which each edge of the graph belongs to at least two cycles in the family. This settles a question raised by Oxley. A certain result known for cycles and cocycles in graphs is extended to matroids. It is shown that for a k-connected regular matroid having circumference c ≥ 2k if C₁ and C₂ are disjoint circuits satisfying r(C₁)+r(C₂)=r(C₁∪C₂), then |C₁|+|C₂|≤2(c-k + 1).     

On thek dimensional Piatetski-Shapiro prime number theorem

Thek-dimensional Piatetski-Shapiro prime number problem fork⩾3 is studied. Let π(x ₁ c ₁,⋯,c _k ) denote the number of primesp withp⩽x, , where 1<c ₁<⋯<c _k are fixed constants. It is proved that π(x;c ₁,⋯,c _k ) has an asymptotic formula ifc ₁ ⁻¹ +⋯+c _k ⁻¹ >k−k/(4k ²+2). Project supported by the National Natural Science Foundation of China (Grant No. 19801021) and the Natural Science Foundation of Shandong Province (Grant No.Q98A02110).     

Generalizations of a Ramsey-theoretic result of chvátal

Chvátal has shown that if T is a tree on n points then r(K_k, T) = (k – 1) (n – 1) + 1, where r is the (generalized) Ramsey number. It is shown that the same result holds when T is replaced by many other graphs. Such a T is called k-good. The results proved all support the conjecture that any large graph that is sufficiently sparse, in the appropriate sense, is k-good.     

Double Arrays,Triple Arrays and Balanced Grids with <Emphasis Type="Italic">v</Emphasis>=<Emphasis Type="Italic">r</Emphasis>+<Emphasis Type="Italic">c</Emphasis> −1

In Theorem 6.1 of McSorley et al. [3] it was shown that, when v=r+c−1, every triple array TA(v,k,λ_rr,λ_cc,k:r× c) is a balanced grid BG(v,k,k:r × c). Here we prove the converse of this Theorem. Our final result is: Let v=r+c−1. Then every triple array is a TA(v,k,c−k,r−k,k:r× c) and every balanced grid is a BG(v,k,k:r× c), and they are equivalent.Communicated by: J.D. Key     

A Characterization of 3-(γ c , 2)-Critical Claw-Free Graphs Which are not 3-γ c -Critical

Let γ _c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ _c -critical if γ _c (G) = k, but γ _c (G + xy) < k for ${xy \in E(\overline {G})}$ . Further, for integer r ≥ 2, G is said to be k-(γ _c , r)-critical if γ _c (G) = k, but γ _c (G + xy) < k for each pair of non-adjacent vertices x and y that are at distance at most r apart. k-γ _c -critical graphs are k-(γ _c , r)-critical but the converse need not be true. In this paper, we give a characterization of 3-(γ _c , 2)-critical claw-free graphs which are not 3-γ _c -critical. In fact, we show that there are exactly four classes of such graphs.     

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     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).     

On Sperner families in which no k sets have an empty intersection, II

Let n_c,d(r, k) denote the maximal cardinality of Sperner families (i.e., XY for all X, Y ε ) on an r-element set satisfying c X d for all X ε and in which no k sets have an empty intersection. n_c,d(r, k) was determined by Frankl (J. Combin. Theory Ser. A 20 (1976), 1–11) if c r/k, and, if c = 0 and d = r, by Frankl and the author (J. Combin. Theory Ser. A 28 (1980), 54–63; Acta Cybernet. 4 (1978), 213–220 for all r and k with exception of 60 values of r if k = 3. In this paper we solve the problem of determination of n_c,d(r, 3) in nearly all unknown cases. In particular, we obtain n_0,r(r, 3) for 33 of the exceptional cases.     

On the chromatic number of the general Kneser-graph

Given integers k, n, 2 < k < n, let us define a graph with vertex set V = {F ?{1, 2, …, n}: ∩F = k}, and (F, F') is an edge if |F ∩ F′| ≤ 1. We show that for n > n₀(k) the chromatic number of this graph is (k - 1)() + rs, where n = (k - 1)s + r, 0 ≤ r < k - 1.     

Positive values of non-homogeneous indefinite quadratic forms of type (1, 4)

Let Г_r,n—r denote the infimum of all number Г > 0 such that for any real indefinite quadratic form inn variables of type (r, n—r), determinantD ≠ 0 and real numbers c₁; c₂,…, c_n, there exist integersx ₁,x₂,…,x_n satisfying 0 < Q(x₁+c₁,x₂ + c₂,…,x_n + c_n) ≤(Г|Z > |)^1/n. All the values of Г_r,n—r are known except for г_1,4. Earlier it was shown that 8 ≤Г_1,4 ≤16. Here we improve the upper bound to get Г_1,4 < 12.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

Characterization of polyanalytic functions by meromorphic extensions from chains of circles

Let C _t = {z ∈ ℂ: |z − c(t)| = r(t), t ∈ (0, 1)} be a C ¹-family of circles in the plane such that lim _t→0+ C _t = {a}, lim _t→1− C _t = {b}, a ≠ b, and |c′(t)|² + |r′(t)|² ≠ 0. The discriminant set S of the family is defined as the closure of the set {c(t) + r(t)w(t), t ∈ [0, 1]}, where w = w(t) is the root of the quadratic equation ̅c′(t)w ² + 2r′(t)w + c′(t) = 0 with |w| < 1, if such a root exists.     

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.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

On numerical experiments with symmetric semigroups generated by three elements and their generalization

We give a simple explanation of numerical experiments of V. Arnold with two sequences of symmetric numerical semigroups, S(4,6+4k,87−4k) and S(9,3+9k,85−9k) generated by three elements. We present a generalization of these sequences by numerical semigroups S(r₁²,r₁r₂+r₁²k,r₃-r₁²k)\mathsf{S}(r_{1}^{2},r_{1}r_{2}+r_{1}^{2}k,r_{3}-r_{1}^{2}k), k∈ℤ, r ₁,r ₂,r ₃∈ℤ⁺, r ₁≥2 and gcd(r ₁,r ₂)=gcd(r ₁,r ₃)=1, and calculate their universal Frobenius number Φ(r ₁,r ₂,r ₃) for the wide range of k providing semigroups be symmetric. We show that this type of semigroups admit also nonsymmetric representatives. We describe the reduction of the minimal generating sets of these semigroups up to {r₁²,r₃-r₁²k}\{r_{1}^{2},r_{3}-r_{1}^{2}k\} for sporadic values of k and find these values by solving the quadratic Diophantine equation.