Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A general class of fuzzy operators,the demorgan class of fuzzy operators and fuzziness measures induced by fuzzy operators

In this paper we examine operators which can be derived from the general solution of functional equations on associativity. We define the characteristics of those functions f(x) which are necessary for the production of operators. We shall show, that with the help of the negation operator for every such function f(x) a function g(x) can be given, from which a disjunctive operator can be derived, and for the three operators the DeMorgan identity is fulfilled. For the fulfillment of the DeMorgan identity the necessary and sufficient conditions are given.We shall also show that an f_λ(x) can be constructed for every f(x), so that for the derived k_λ(x,y) and d_λ(x,y) lim_λ→∞k_λ(x,y) and lim_λ→∞d_λ(x,y) = max(x,y).As Yager's operator is not reducible, for every λ there exists an α, for which, in case x < α and y<α, k_λ(x,y) = 0.We shall give an f(x) which has the characteristics of Yager's operator, and which is strictly monotone.Finally we shall show, that with the help of all those f(x), which are necessary when constructing a k(x,y), an F(x) can be constructed which has the properties of the measures of fuzziness introduced by A. De Luca and S. Termini. Some classical fuzziness measures are obtained as special cases of our system.     

Sobolev Duals for Random Frames and ΣΔ Quantization of Compressed Sensing Measurements

Quantization of compressed sensing measurements is typically justified by the robust recovery results of Candès, Romberg and Tao, and of Donoho. These results guarantee that if a uniform quantizer of step size δ is used to quantize m measurements y=Φx of a k-sparse signal x∈? ^N , where Φ satisfies the restricted isometry property, then the approximate recovery x ^# via ? ₁-minimization is within O(δ) of x. The simplest and commonly assumed approach is to quantize each measurement independently. In this paper, we show that if instead an rth-order ΣΔ (Sigma–Delta) quantization scheme with the same output alphabet is used to quantize y, then there is an alternative recovery method via Sobolev dual frames which guarantees a reduced approximation error that is of the order δ(k/m)^(r?1/2)α for any 0<α<1, if m? _r,α k(logN)^1/(1?α). The result holds with high probability on the initial draw of the measurement matrix Φ from the Gaussian distribution, and uniformly for all k-sparse signals x whose magnitudes are suitably bounded away from zero on their support.     

Weakly Singular Integral Operators in Weighted L∞–Spaces

We study integral operators on (−1, 1) with kernels k(x, t) which may have weak singularities in (x, t) with x ∈N₁, t ∈N₂, or x=t, where N₁,N₂ are sets of measure zero. It is shown that such operators map weighted L^∞–spaces into certain weighted spaces of smooth functions, where the degree of smoothness is the higher the smoother the kernel k(x, t) as a function in x is. The spaces of smooth function are generalizations of the Ditzian-Totik spaces which are defined in terms of the errors of best weighted uniform approximation by algebraic polynomials.     

Analytic solutions to a class of nonlinear infinite-delay-differential equations

The infinite-delay-differential equations (IDDEs) are studied and the analytic solution of a class of nonlinear IDDEs is presented based on the characteristics of the reproducing kernel space W₂[0,∞). Besides, the exact solution is represented in the form of series. It is proved that the n-term approximation un(x) converges to the exact solution u(x) of the IDDEs. Moreover, the approximate error of un(x) is monotone decreasing. The results of experiments showed that the proposed method in this paper is computationally efficient.     

Product integration of logarithmic singular integrands based on cubic splines

This paper is concerned with the practical evaluation of the product integral ∫¹_{? 1}f(x)k(x)dx for the case when k(x) = In|x - λ|, λ? (?1, +1) and f is bounded in [?1, +1]. The approximation is a quadrature rule

where the weights {w_n,n,i} are chosen to be exact when f is given by a linear combination of a chosen set of functions {φ_n,j}. In this paper the functions {φ_n,j} are chosen to be cubic B-splines. An error bound for product quadrature rules based on cubic splines is provided. Examples that test the performance of the product quadrature rules for different choices of the function are given. A comparison is made with product quadrature rules based on first kind Chebyshev polynomials.     

A RIGOROUS DERIVATION OF THE GROSS-PITAEVSKII HIERARCHY FOR WEAKLY COUPLED TWO-DIMENSIONAL BOSONS

In this article, we consider the dynamics of N two-dimensional boson systems interacting through a pair potential N-1Va(xi-xj) where Va(x) = a-2V (x/a). It is well known that the Gross-Pitaevskii (GP) equation is a nonlinear Schrdinger equation and the GP hierarchy is an infinite BBGKY hierarchy of equations so that if ut solves the GP equation, then the family of k-particle density matrices {k ut, k ≥ 1} solves the GP hierarchy. Denote by ψN,t the solution to the N-particle Schrdinger equation. Under the assumption that a = N-ε for 0 ε 3/4, we prove that as N →∞ the limit points of the k-particle density matrices of ψN,t are solutions of the GP hierarchy with the coupling constant in the nonlinear term of the GP equation given by ∫V (x) dx.     

Adding machines, kneading maps, and endpoints

Given a unimodal map f, let I=[c₂,c₁] denote the core and set E={(x₀,x₁,…)∈(I,f)|xi∈ω(c,f) for all i∈N}. It is known that there exist strange adding machines embedded in symmetric tent maps f such that the collection of endpoints of (I,f) is a proper subset of E and such that limk→∞Q(k)≠∞, where Q(k) is the kneading map.We use the partition structure of an adding machine to provide a sufficient condition for x to be an endpoint of (I,f) in the case of an embedded adding machine. We then show there exist strange adding machines embedded in symmetric tent maps for which the collection of endpoints of (I,f) is precisely E. Examples of this behavior are provided where limk→∞Q(k) does and does not equal infinity, and in the case where limk→∞Q(k)=∞, the collection of endpoints of (I,f) is always E.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

Maximal Collections of Intersecting Arithmetic Progressions

Let N _t (k) be the maximum number of k-term arithmetic progressions of real numbers, any two of which have t points in common. We determine N ₂(k) for prime k and all large k, and give upper and lower bounds for N _t (k) when t 3.* Research supported in part by NSF grant DMS-0070618.     

On tense modules for extended algebras over rational fields

Let k(x) be the field of fractions of the polynomial algebra k[x] over the field k. We prove that, for an arbitrary finite dimensional k-algebra Λ, any finitely generated Λ ⊗_k k(x)-module M such that its minimal projective presentation admits no non-trivial selfextension is of the form M ≅ N^k(x), for some finitely generated Λ-module N. Some consequences are derived for tilting modules over the rational algebra Λ ⊗_k k(x) and for some generic modules for Λ. Received: 24 November 2003; revised: 11 February 2005     

Stability of Friedrichs's scheme in the maximum norm for hyperbolic systems in one space dimension

We are concerned with Friedrichs's scheme for an initial value problem u_t(t, x) = A(t, x)u_x(t, x), u(0, x) = u₀(x), where u₀(x) belongs to L_∞, not to L₂. We show that Friedrichs's scheme is stable in the maximum norm ·_L∞, provided that the system is regularly hyperbolic and that the eigenvalues d_i(t, x) (i = 1,2,..., N) of the N XN matrix A(t, x) satisfy the conditions 1±λd_i(t, x)?0 (i = 1,2,..., N), where λ is a mesh ratio.     

The Kth largest eigenvalue of a tree

Let λ_k(T) be the kth eigenvalue of a tree, [x] the largest integer not greater than x. It is shown that a tree with n vertices has λ_k(T)⩽√[(n-2)/k] for 2⩽k⩽[n/2], and this upper bound is best possible for n≡1 mod k.     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.     

Sums over numbers with restricted prime factors

For k a non-negative integer, let P_k(n) denote the kth largest prime factor of n where P₀(n) = +∞ and if the number of prime factors of n is less than k, then P_k(n) = 1. We shall study the asymptotic behavior of the sum Ψ_k(x, y; g) = Σ_{1 ≤ n ≤ x, Pk(n) ≤ y}g(n), where g(n) is an arithmetic function satisfying certain general conditions regarding its behavior on primes. The special case where g(n) = μ(n), the Möbius function, is discussed as an application.     

Spectral bounds for the clique and independence numbers of graphs

We obtain a sequence k₁(G) ≤ k₂(G) ≤ … ≤ k_n(G) of lower bounds for the clique number (size of the largest clique) of a graph G of n vertices. The bounds involve the spectrum of the adjacency matrix of G. The bound k₁(G) is explicit and improves earlier known theorems. The bound k₂(G) is also explicit, and is shown to improve on the bound from Brooks' theorem even for regular graphs. The bounds k₃,…, k_r are polynomial-time computable, where r is the number of positive eigenvalues of G.     

A method of multipliers for mathematical programming problems with equality and inequality constraints

This paper deals with the numerical solution of the general mathematical programming problem of minimizing a scalar functionf(x) subject to the vector constraints φ(x)=0 and ψ(x)≥0. The approach used is an extension of the Hestenes method of multipliers, which deals with the equality constraints only. The above problem is replaced by a sequence of problems of minimizing the augmented penalty function Ω(x, λ, μ,k)=f(x)+λ ^T φ(x)+kφ ^T (x)φ(x) ?μ ^T \(\tilde \psi \) (x)+k \(\tilde \psi \) ^T (x) \(\tilde \psi \) (x). The vectors λ and μ, μ ≥ 0, are respectively the Lagrange multipliers for φ(x) and \(\tilde \psi \) (x), and the elements of \(\tilde \psi \) (x) are defined by \(\tilde \psi \) _(j)(x)=min[ψ_(j)(x), (1/2k) μ_(j)]. The scalark>0 is the penalty constant, held fixed throughout the algorithm. Rules are given for updating the multipliers for each minimization cycle. Justification is given for trusting that the sequence of minimizing points will converge to the solution point of the original problem.     

Determination of the Unknown Cauchy Data in a Linear Parabolic Problem from the Measured Data at the Final Time

The problem of determining the initial value u(x, 0) = μ ₀(x) in the parabolic equation u _t = (k(x)u _x (x, t)) _x + F(x, t) from the final overdetermination μ _T (x) = u(x, T) is formulated. It is proved that the Fréchet derivative of the cost functional ${{J(\mu_0) = \|\mu_T(x) - u(x, T)\|_0^2}}$ can be formulated via the solution of the adjoint parabolic problem. Lipschitz continuity of the gradient is proved. The existence of a quasisolution of the considered inverse problem is proved. A monotone iteration scheme is obtained based on the gradient method.     

On the stability properties of perturbed linear nonstationary systems

Several results are presented that relate the stability properties of a perturbed linear nonstationary system ?(t) = (A(t) + B(t)) x(t) to those of an unperturbed linear system ?(t) = A(t) x(t). Similarly, the stability properties of the discrete system x_{k + 1} = (A_k + B_k) x_k are related to those of x_{k + 1} = A_kx_k.