Boundary effects on convergence rates for Tikhonov regularization

We consider the Tikhonov regularizer f_λ of a smooth function f ε H^2m[0, 1], defined as the solution (see [1]) to We prove that if f^(j)(0) = f^(j)(1) = 0, J = m, …, k < 2m − 1, then ¦f − f_λ¦_j² Rλ^{(2k − 2j + 3)/2m}, J = 0, …, m. A detailed analysis is given of the effect of the boundary on convergence rates.     

On the enumeration of parking functions by leading terms

Let x=(x₁,…,x_n) be a sequence of positive integers. An x-parking function is a sequence (a₁,…,a_n) of positive integers whose non-decreasing rearrangement b₁b_n satisfies b_ix₁++x_i. In this paper we give a combinatorial approach to the enumeration of (a,b,…,b)-parking functions by their leading terms, which covers the special cases x=(1,…,1), (a,1,…,1), and (b,…,b). The approach relies on bijections between the x-parking functions and labeled rooted forests. To serve this purpose, we present a simple method for establishing the required bijections. Some bijective results between certain sets of x-parking functions of distinct leading terms are also given.     

Asymptotic Behavior of Sobolev-Type Orthogonal Polynomials on the Unit Circle

We study the asymptotic behavior of the sequence of polynomials orthogonal with respect to the discrete Sobolev inner product on the unit circle

Full-size image

where f(Z)=(f(z₁), …, f^(l₁)(z₁), …, f(z_m), …, f^(l_m)(z_m)), A is a M×M positive definite matrix or a positive semidefinite diagonal block matrix, M=l₁+…+l_m+m, dμ belongs to a certain class of measures, and |z_i|>1, i=1, 2, …, m.     

Generalized Sets of Lengths

LetRbe a Dedekind domain and (R) the set of irreducible elements ofR. In this paper, we study the sets _R(n) = {m | α₁,…,α_n, β₁,…,β_m (R) such that α₁,…,α_n = β₁,…,β_m}, wherenis a positive integer. We show, in constrast to indications in some earlier work, that the sets _R(n) are not completely determined by the Davenport constant of the class group ofR. We offer some specific constructions for Dedekind domains with small class groups, and show how these sets are generalizations of the sets studied earlier by Geroldinger [[9], [10]].     

Extremal values of continuants and transcendence of certain continued fractions

We prove a criterion for the transcendence of continued fractions whose partial quotients are contained in a finite set {b₁,…,b_r} of positive integers such that the density of occurrences of b_i in the sequence of partial quotients exists for 1ir. As an application we study continued fractions [0,a₁,a₂,a₃,…] with a_n=1+([nθ]modd) where θ is irrational and d2 is a positive integer.     

On Chebyshev–Markov Rational Functions over Several Intervals

Chebyshev–Markov rational functions are the solutions of the following extremal problem

Full-size image

withKbeing a compact subset of andω_n(x) being a fixed real polynomial of degree less thann, positive onK. A parametric representation of Chebyshev–Markov rational functions is found forK=[b₁, b₂]…[b_2p−1, b_2p], −∞<b₁b₂<…<b_2p−1b_2p<+∞ in terms of Schottky–Burnside automorphic functions.     

Gabor dual spline windows

A method is presented for constructing dual Gabor window functions that are polynomial splines. The spline windows are supported in [−1,1], with a knot at x=0, and can be taken C^m smooth and symmetric. The translation and modulation parameters satisfy a=1 and 0<b1/2. The full range 0<ab<1 is handled by introducing an additional knot. Many explicit examples are found.     

Nonnegative solutions of a nonlinear recurrence

Orthonormal polynomials with weight ¦τ¦ exp(−τ⁴) have leading coefficients with recurrence properties which motivate the more general equations ξ_m(ξ_{m − 1} + ξ_m + ξ_{m + 1}) = γ_m², M = 1, 2,…, where ξ_o is a fixed nonnegative value and γ₁, γ₂,… are positive constants. For this broader problem, the existence of a nonnegative solution is proved and criteria are found for its uniqueness. Then, for the motivating problem, an asymptotic expansion of its unique nonnegative solution is obtained and a fast computational algorithm, with error estimates, is given.     

Linked graphs with restricted lengths

A graph G is k-linked if G has at least 2k vertices, and for every sequence x₁,x₂,…,x_k,y₁,y₂,…,y_k of distinct vertices, G contains k vertex-disjoint paths P₁,P₂,…,P_k such that P_i joins x_i and y_i for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m₁,m₂,…,m_k)-linked if, in addition, for any k-tuple (d₁,d₂,…,d_k) of natural numbers, the paths P₁,P₂,…,P_k can be chosen such that P_i has length d_i modulo m_i for i=1,2,…,k. Thomassen showed that, for each k-tuple (m₁,m₂,…,m_k) of odd positive integers, there exists a natural number f(m₁,m₂,…,m_k) such that every f(m₁,m₂,…,m_k)-connected graph is modulo (m₁,m₂,…,m_k)-linked. For m₁=m₂=…=m_k=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo (2,2,…,2)-linked or there is XV(G) such that |X|4k−3 and G−X is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m₁,m₂,…,m_k)max{14(m₁+m₂++m_k)−4k,6(m₁+m₂++m_k)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some m_i be even integers. Let (m₁,m₂,…,m_k) be a k-tuple of natural numbers and ℓk such that m_i is odd for each i with ℓ+1ik. If G is 45(m₁+m₂++m_k)-connected, then either G has a vertex set X of order at most 2k+2ℓ−3+δ(m₁,…,m_ℓ) such that G−X is bipartite or G is modulo (2m₁,…,2m_ℓ,m_ℓ+1,…,m_k)-linked, where

Our results generalize several known results on parity-linked graphs.     

Characterization of generalized convex functions by their best approximation in sign-monotone norms

Let {u₀, u₁,… u_{n − 1}} and {u₀, u₁,…, u_n} be Tchebycheff-systems of continuous functions on [a, b] and let f ε C[a, b] be generalized convex with respect to {u₀, u₁,…, u_{n − 1}}. In a series of papers ([1], [2], [3]) D. Amir and Z. Ziegler discuss some properties of elements of best approximation to f from the linear spans of {u₀, u₁,…, u_{n − 1}} and {u₀, u₁,…, u_n} in the L_p-norms, 1 p ∞, and show (under different conditions for different values of p) that these properties, when valid for all subintervals of [a, b], can characterize generalized convex functions. Their methods of proof rely on characterizations of elements of best approximation in the L_p-norms, specific for each value of p. This work extends the above results to approximation in a wider class of norms, called “sign-monotone,” [6], which can be defined by the property: ¦ f(x)¦ ¦ g(x)¦,f(x)g(x) 0, a x b, imply f g . For sign-monotone norms in general, there is neither uniqueness of an element of best approximation, nor theorems characterizing it. Nevertheless, it is possible to derive many common properties of best approximants to generalized convex functions in these norms, by means of the necessary condition proved in [6]. For {u₀, u₁,…, u_n} an Extended-Complete Tchebycheff-system and f ε C⁽ⁿ⁾[a, b] it is shown that the validity of any of these properties on all subintervals of [a, b], implies that f is generalized convex. In the special case of f monotone with respect to a positive function u₀(x), a converse theorem is proved under less restrictive assumptions.     

Limit distributions and one-parameter groups of linear operators on Banach spaces

Let = {U_t: t > 0} be a strongly continuous one-parameter group of operators on a Banach space X and Q be any subset of a set (X) of all probability measures on X. By (Q; ) we denote the class of all limit measures of {U_tn(μ₁ * μ₂*…*μ_n)*δ_xn}, where {μ_n}Q, {x_n}X and measures U_tnμ_j (j=1, 2,…, n; N=1, 2,…) form an infinitesimal triangular array. We define classes L_m( ) as follows: L₀( )= ( (X); ), L_m( )= (L_m−1( ); ) for m=1, 2,… and L_∞( )=_m=0^∞L_m( ). These classes are analogous to those defined earlier by Urbanik on the real line. Probability distributions from L_m( ), m=0, 1, 2,…, ∞, are described in terms of their characteristic functionals and their generalized Poisson exponents and Gaussian covariance operators.     

Gray codes for column-convex polyominoes and a new class of distributive lattices

We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of m-tuples [S₁]×[S₂]××[S_m], where each S_i>1 and [S_i]={0,1,…,S_i−1}, and the cover relations are (p₁,p₂,…,p_m)(p₁+1,p₂,…,p_m) and (p₁,p₂,…,p_j,p_j+1,…,p_m)(p₁,p₂,…,p_j−1,p_j+1+1,…,p_m). We also discuss some properties of this lattice.     

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

We consider the bounded integer knapsack problem (BKP) , subject to: , and x_j{0,1,…,m_j},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=max_j=1,…,nw_j. The respective complexity of the unbounded case with m_j=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.     

On Generalized Hermite–Fejér Interpolation of Lagrange Type on the Chebyshev Nodes

For fC[−1, 1], let H_m, n(f, x) denote the (0, 1, …,anbsp;m) Hermite–Fejér (HF) interpolation polynomial of f based on the Chebyshev nodes. That is, H_m, n(f, x) is the polynomial of least degree which interpolates f(x) and has its first m derivatives vanish at each of the zeros of the nth Chebyshev polynomial of the first kind. In this paper a precise pointwise estimate for the approximation error |H_2m, n(f, x)−f(x)| is developed, and an equiconvergence result for Lagrange and (0, 1, …, 2m) HF interpolation on the Chebyshev nodes is obtained. This equiconvergence result is then used to show that a rational interpolatory process, obtained by combining the divergent Lagrange and (0, 1, …, 2m) HF interpolation methods on the Chebyshev nodes, is convergent for all fC[−1, 1].     

A new approach to Euler splines

Starting from the exponential Euler polynomials discussed by Euler in “Institutions Calculi Differentialis,” Vol. II, 1755, the author introduced in “Linear operators and approximation,” Vol. 20, 1972, the so-called exponential Euler splines. Here we describe a new approach to these splines. Let t be a constant such that t=|t|e^iα, −π<α<π,t≠0,t≠1.. Let S₁(x:t) be the cardinal linear spline such that S₁(v:t) = t^v for all v ε Z. Starting from S₁(x:t) it is shown that we obtain all higher degree exponential Euler splines recursively by the averaging operation . Here S_n(x:t) is a cardinal spline of degree n if n is odd, while is a cardinal spline if n is even. It is shown that they have the properties S_n(v:t) = t^v for v ε Z.     

Pairwise intersections and forbidden configurations

Let f_m(a,b,c,d) denote the maximum size of a family of subsets of an m-element set for which there is no pair of subsets with

By symmetry we can assume a≥d and b≥c. We show that f_m(a,b,c,d) is Θ(m^a+b−1) if either b>c or a,b≥1. We also show that f_m(0,b,b,0) is Θ(m^b) and f_m(a,0,0,d) is Θ(m^a). The asymptotic results are as m→∞ for fixed non-negative integers a,b,c,d. This can be viewed as a result concerning forbidden configurations and is further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Complete Intersection Theorem of Ahlswede and Khachatrian, which is of independent interest.     

Persistence, contractivity and global stability in logistic equations with piecewise constant delays

We establish sufficient conditions for the persistence and the contractivity of solutions and the global asymptotic stability for the positive equilibrium N^*=1/(a+∑_i=0^mb_i) of the following differential equation with piecewise constant arguments:

where r(t) is a nonnegative continuous function on [0,+∞), r(t)0, ∑_i=0^mb_i>0, b_i0, i=0,1,2,…,m, and a+∑_i=0^mb_i>0. These new conditions depend on a,b₀ and ∑_i=1^mb_i, and hence these are other type conditions than those given by So and Yu (Hokkaido Math. J. 24 (1995) 269–286) and others. In particular, in the case m=0 and r(t)≡r>0, we offer necessary and sufficient conditions for the persistence and contractivity of solutions. We also investigate the following differential equation with nonlinear delay terms:

where r(t) is a nonnegative continuous function on [0,+∞), r(t)0, 1−ax−g(x,x,…,x)=0 has a unique solution x^*>0 and g(x₀,x₁,…,x_m)C¹[(0,+∞)×(0,+∞)××(0,+∞)].     

Convergence of Derivatives of Optimal Nodal Splines

Optimal nodal spline interpolantsWfof ordermwhich have local support can be used to interpolate a continuous functionfat a set of mesh points. These splines belong to a spline space with simple knots at the mesh points as well as atm−2 arbitrary points between any two mesh points and they reproduce polynomials of orderm. It has been shown that, for a sequence of locally uniform meshes, these splines converge uniformly for anyfCas the mesh norm tends to zero. In this paper, we derive a set of sufficient conditions on the sequence of meshes for the uniform convergence ofD^jWftoD^jfforfC^sandj=1, …, s<m. In addition we give a bound forD^rWfwiths<r<m. Finally, we use optimal nodal spline interpolants for the numerical evaluation of Cauchy principal value integrals.     

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

On Rado numbers for

For all integers m3 and all natural numbers a₁,a₂,…,a_m−1, let n=R(a₁,a₂,…,a_m−1) represent the least integer such that for every 2-coloring of the set {1,2,…,n} there exists a monochromatic solution to

a₁x₁+a₂x₂++a_m−1x_m−1=x_m.