Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Strong limit theorems for quasi-orthogonal random fields

This is a systematic and unified treatment of a variety of seemingly different strong limit problems. The main emphasis is laid on the study of the a.s. behavior of the rectangular means ζ_mn = 1/(λ₁(m) λ₂(n)) Σ_i=1^m Σ_k=1ⁿ X_ik as either max{m, n} → ∞ or min{m, n} → ∞. Here {X_ik: i, k ≥ 1} is an orthogonal or merely quasi-orthogonal random field, whereas {λ₁(m): m ≥ 1} and {λ₂(n): n ≥ 1} are nondecreasing sequences of positive numbers subject to certain growth conditions. The method applied provides the rate of convergence, as well. The sufficient conditions obtained are shown to be the best possible in general. Results on double subsequences and 1-parameter limit theorems are also included.     

Convergence of greedy approximation for the trigonometric system

Summary We study the following nonlinear method of approximation by trigonometric polynomials in this paper. For a periodic function f we take as an approximant a trigonometric polynomial of the form G_m(f ) := ∑_kЄΛ f^(k) e ^{(i k,x)}, where ΛˆZ^d is a set of cardinality m containing the indices of the m biggest (in absolute value) Fourier coefficients f^ (k) of function f . Note that G_m(f ) gives the best m-term approximant in the L₂-norm and, therefore, for each f ЄL₂, ║f-G_m(f )║₂→0 as m →∞. It is known from previous results that in the case of p ≠2 the condition f ЄL_p does not guarantee the convergence ║f-G_m(f )║_p→0 as m →∞.. We study the following question. What conditions (in addition to f ЄL_p) provide the convergence ║f-G_m(f )║_p→0 as m →∞? In our previous paper [10] in the case 2< p ≤∞ we have found necessary and sufficient conditions on a decreasing sequence {A_n}_n=1^∞ to guarantee the L_p-convergence of {G_m(f )} for all f ЄL_p , satisfying a_n (f ) ≤A_n , where {a_n (f )} is a decreasing rearrangement of absolute values of the Fourier coefficients of f. In this paper we are looking for necessary and sufficient conditions on a sequence {M (m)} such that the conditions f ЄL_p and ║G_M(m)(f ) - G_m(f )║_p →0 as m →∞ imply ║f - G_m(f )║_p →0 as m →∞. We have found these conditions in the case when p is an even number or p = ∞.     

On the L convergence of Lagrange interpolating entire functions of exponential type

Let f: be a continuous, 2π-periodic function and for each n ε let t_n(f; ·) denote the trigonometric polynomial of degree n interpolating f in the points 2kπ/(2n + 1) (k = 0, ±1, …, ±n). It was shown by J. Marcinkiewicz that lim_{n → ∞} ∝₀^2π¦f(θ) − t_n(f θ)¦^p dθ = 0 for every p > 0. We consider Lagrange interpolation of non-periodic functions by entire functions of exponential type τ > 0 in the points kπ/τ (k = 0, ± 1, ± 2, …) and obtain a result analogous to that of Marcinkiewicz.     

The Lebesgue Constant for Higher Order Hermite-Fejér Interpolation on the Chebyshev Nodes

For a fixed integer m ≥ 0, and for n = 1, 2, 3, ..., let λ_{2m, n}(x) denote the Lebesgue function associated with (0, 1,..., 2m) Hermite-Fejér polynomial interpolation at the Chebyshev nodes {cos[(2k−1) π/(2n)]: k=1, 2, ..., n}. We examine the Lebesgue constant Λ_{2m, n} max{λ_{2m, n}(x): −1 ≤ x ≤ 1}, and show that Λ_{2m, n} = λ_{m, n}(1), thereby generalising a result of H. Ehlich and K. Zeller for Lagrange interpolation on the Chebyshev nodes. As well, the infinite term in the asymptotic expansion of Λ_{2m, n)} as n → ∞ is obtained, and this result is extended to give a complete asymptotic expansion for Λ_{2, n}.     

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.     

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     

Asymptotic Properties of Zeros of Hypergeometric Polynomials

In a paper by K. Driver and P. Duren (1999, Numer. Algorithms21, 147–156) a theorem of Borwein and Chen was used to show that for each k the zeros of the hypergeometric polynomials F(−n, kn+1; kn+2; z) cluster on the loop of the lemniscate {z: |z^k(1−z)|=k^k/(k+1)^k+1}, with Re{z}>k/(k+1) as n→∞. We now supply a direct proof which generalizes this result to arbitrary k>0, while showing that every point of the curve is a cluster point of zeros. Examples generated by computer graphics suggest some finer asymptotic properties of the zeros.     

2-Colored triangles in edge-colored complete graphs, II

The largest number n = n(k) for which there exists a k-coloring of the edges of k_n with every triangle 2-colored is found to be n(k) = 2^r5^m, where k = 2m + r and r = 0 or 1, and all such colorings are given. We also prove the best possible result that a k-colored K_p satisfying 1 < k < 1 + √p contains at most k − 2 vertices not in a bichromatic triangle.     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

Uniform Estimates for a Class of Evolution Equations

L^∞ estimates are derived for the oscillatory integral ∫⁺₀^∞e^{−i(xλ + (1/m) tλm)}a(λ) dλ, where 2 ≤ m and (x, t) × ₊. The amplitude a(λ) can be oscillatory, e.g., a(λ) = e^{it (λ)} with (λ) a polynomial of degree ≤ m − 1, or it can be of polynomial type, e.g., a(λ) = (1 + λ)^k with 0 ≤ k ≤ (m − 2). The estimates are applied to the study of solutions of certain linear pseudodifferential equations, of the generalized Schrödinger or Airy type, and of associated semilinear equations.     

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

Weak Asymptotics for the Generating Polynomials of the Stirling Numbers of the Second Kind

For the horizontal generating functions P_n(z)=∑ⁿ_k=1 S(n, k) z^k of the Stirling numbers of the second kind, strong asymptotics are established, as n→∞. By using the saddle point method for Q_n(z)=P_n(nz) there are two main results: an oscillating asymptotic for z(−e, 0) and a uniform asymptotic on every compact subset of \[−e, 0]. Finally, an Airy asymptotic in the neighborhood of −e is deduced.     

L∞-upper bound of L2-projections onto splines at a geometric mesh

For an integer k 1 and a geometric mesh (qⁱ)_−∞^∞ with q ε (0, ∞), let M_i,k(x): = k[q^{i + k}](· − x)₊^{k − 1}, N_i,k(x): = (q^{i + k} − qⁱM_i,k(x)/k, and let A_k(q) be the Gram matrix (∝M_i,kN_j,k)_i,jεz. It is known that A_k(q)⁻¹_∞ is bounded independently of q. In this paper it is shown that A_k(q)⁻¹_∞ is strictly decreasing for q in [1, ∞). In particular, the sharp upper bound and lower bound for A_k (q)⁻¹ are obtained: for all q ε (0, ∞).     

On the Erd s-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings

A link between Ramsey numbers for stars and matchings and the Erd s-Ginzburg-Ziv theorem is established. Known results are generalized. Among other results we prove the following two theorems. Theorem 5. Let m be an even integer. If c : e (K_2m−1)→{0, 1,…, m−1} is a mapping of the edges of the complete graph on 2m−1 vertices into {0, 1,…, m−1}, then there exists a star K_1,m in K_2m−1 with edges e₁, e₂,…, e_m such that c(e₁)+c(e₂)++c(e_m)≡0 (mod m). Theorem 8. Let m be an integer. If c : e(K^r_(r+1)m−1)→{0, 1,…, m−1} is a mapping of all the r-subsets of an (r+1)m−1 element set S into {0, 1,…, m−1}, then there are m pairwise disjoint r-subsets Z₁, Z₂,…, Z_m of S such that c(Z₁)+c(Z₂)++c(Z_m)≡0 (mod m).     

Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time

For a given undirected graphG = (V, E, c_G) with edges weighted by nonnegative realsc_G:E → R ⁺ , let Λ_G(k) stand for the minimum amount of weights which needs to be added to makeG k-edge-connected, and letG*(k) be the resulting graph obtained fromG. This paper first shows that function Λ_Gover the entire rangek [0, +∞] can be computed inO(nm + n² log n) time, and then shows that allG*(k) in the entire range can be obtained fromO(n log n) weighted cycles, and such cycles can be computed inO(nm + n² log n) time, wherenandmare the numbers of vertices and edges, respectively.     

Rainbow Numbers for Cycles with Pendant Edges

A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K _n with no rainbow copy of H. The rainbow number rb(n, H) is the minimum number of colors such that any edge-coloring of K _n with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers. We show that for n ≥ k + 1, where C _k ⁺ denotes a cycle C _k with a pendant edge.     

On the Maximal Multiplicity of Parts in a Random Integer Partition

We study the asymptotic behavior of the maximal multiplicity μ_n = μ_n(λ) of the parts in a partition λ of the positive integer n, assuming that λ is chosen uniformly at random from the set of all such partitions. We prove that πμ_n/(6n)^1/2 converges weakly to max _jX_j/j as n→∞, where X₁, X₂, … are independent and exponentially distributed random variables with common mean equal to 1.2000 Mathematics Subject Classification: Primary—05A17; Secondary—11P82, 60C05, 60F05     

Asymptotic Behaviour of Best lp-Approximations from Affi ne Subspaces

In this paper we consider the problem of best approximation in ℓ_pⁿ, 1<p∞. If h_p, 1<p<∞, denotes the best ℓ_p-approximation of the element h ⁿ from a proper affine subspace K of ⁿ, hK, then lim_p→∞h_p=h_∞^*, where h_∞^* is a best uniform approximation of h from K, the so-called strict uniform approximation. Our aim is to prove that for all r there are α_j ⁿ, 1jr, such that

Full-size image

, with γ_p^{(r) n} and γ_p^(r)= (p^−r−1).