Completions of -algebras

A μ-algebra is a model of a first-order theory that is an extension of the theory of bounded lattices, that comes with pairs of terms (f,μ_x.f) where μ_x.f is axiomatized as the least prefixed point of f, whose axioms are equations or equational implications.Standard μ-algebras are complete meaning that their lattice reduct is a complete lattice. We prove that any nontrivial quasivariety of μ-algebras contains a μ-algebra that has no embedding into a complete μ-algebra.We then focus on modal μ-algebras, i.e. algebraic models of the propositional modal μ-calculus. We prove that free modal μ-algebras satisfy a condition–reminiscent of Whitman’s condition for free lattices–which allows us to prove that (i) modal operators are adjoints on free modal μ-algebras, (ii) least prefixed points of Σ₁-operations satisfy the constructive relation μ_x.f=_n≥0fⁿ(). These properties imply the following statement: the MacNeille–Dedekind completion of a free modal μ-algebra is a complete modal μ-algebra and moreover the canonical embedding preserves all the operations in the class of the fixed point alternation hierarchy.     

The topological structure of fuzzy sets with endograph metric

For a non-degenerate convex subset Y of the n-dimensional Euclidean space Rⁿ, let be the family of all fuzzy sets ofRⁿ, which are upper-semicontinuous, fuzzy convex and normal with compact supports contained in Y. We show that the space with the topology of endograph metric is homeomorphic to the Hilbert cube Q=[-1,1]^ω iff Y is compact; and the space is homeomorphic to {(x_n)Q:sup|x_n|<1} iff Y is non-compact and locally compact.     

Highly connected coloured subgraphs via the regularity lemma

For integers , n≥k and r≥s, let m(n,r,s,k) be the largest (in order) k-connected component with at most s colours one can find in any r-colouring of the edges of the complete graph K_n on n vertices. Bollobás asked for the determination of m(n,r,s,k).Here, bounds are obtained in the cases s=1,2 and k=o(n), which extend results of Liu, Morris and Prince. Our techniques use Szemerédi’s Regularity Lemma for many colours.We shall also study a similar question for bipartite graphs.     

Christoffel-type functions for -orthogonal polynomials for Freud weights

This paper gives upper and lower bounds of the Christoffel-type functions , for the m-orthogonal polynomials for a Freud weight W=e^-Q, which are given as follows. Let a_n=a_n(Q) be the nth Mhaskar–Rahmanov–Saff number, φ_n(x)=max{n^-2/3,1-|x|/a_n}, and d>0. Assume that QC(R) is even, , and for some A,B>1

Then for xR

and for |x|a_n(1+dn^-2/3)

     

Two new modified Gauss–Seidel methods for linear system with -matrices

In 2002, H. Kotakemori et al. proposed the modified Gauss–Seidel (MGS) method for solving the linear system with the preconditioner [H. Kotakemori, K. Harada, M. Morimoto, H. Niki, A comparison theorem for the iterative method with the preconditioner () J. Comput. Appl. Math. 145 (2002) 373–378]. Since this preconditioner is constructed by only the largest element on each row of the upper triangular part of the coefficient matrix, the preconditioning effect is not observed on the nth row. In the present paper, to deal with this drawback, we propose two new preconditioners. The convergence and comparison theorems of the modified Gauss–Seidel methods with these two preconditioners for solving the linear system are established. The convergence rates of the new proposed preconditioned methods are compared. In addition, numerical experiments are used to show the effectiveness of the new MGS methods.     

Widths of weighted Sobolev classes on the ball

We study the Kolmogorov n-widths and the linear n-widths of weighted Sobolev classes on the unit ball B^d in L_q,μ, where L_q,μ, 1≤q≤∞, denotes the weighted L_q space of functions on B^d with respect to weight . Optimal asymptotic orders of and as n→∞ are obtained for all 1≤p,q≤∞ and μ≥0.     

Optimality conditions for multiple objective fractional subset programming with ( , ρ,σ,θ )-V-type-I and related non-convex functions

In this paper, we introduce a new class of generalized convex n-set functions, called ( , ρ,σ,θ)-V-Type-I and related non-convex functions, and then establish a number of parametric and semi-parametric sufficient optimality conditions for the primal problem under the aforesaid assumptions. This work partially extends an earlier work of [G.J. Zalmai, Efficiency conditions and duality models for multiobjective fractional subset programming problems with generalized ( , α, ρ, θ)-V-convex functions, Comput. Math. Appl. 43 (2002) 1489–1520] to a wider class of functions.     

Approximating the maximum 2- and 3-edge-colorable subgraph problems

For a fixed value of a parameter k≥2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be -hard for all k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 and k=3, having approximation ratios of 5/6 and 4/5, respectively.     

Second-order symmetric duality with cone constraints

Wolfe and Mond–Weir type second-order symmetric duals are formulated and appropriate duality theorems are established under η-bonvexity/η-pseudobonvexity assumptions. This formulation removes several omissions in an earlier second-order primal dual pair introduced by Devi [Symmetric duality for nonlinear programming problems involving η-bonvex functions, European J. Oper. Res. 104 (1998) 615–621].     

Complexity of the min–max (regret) versions of min cut problems

This paper investigates the complexity of the min–max and min–max regret versions of the min s–t cut and min cut problems. Even if the underlying problems are closely related and both polynomial, the complexities of their min–max and min–max regret versions, for a constant number of scenarios, are quite contrasted since they are respectively strongly NP-hard and polynomial. However, for a non-constant number of scenarios, these versions become strongly NP-hard for both problems. In the interval scenario case, min–max versions are trivially polynomial. Moreover, for min–max regret versions, we obtain the same contrasted results as for a constant number of scenarios: min–max regret min s–t cut is strongly NP-hard whereas min–max regret min cut is polynomial.     

A filtration of -Catalan numbers

The operator of F. Bergeron, Garsia, Haiman and Tesler [F. Bergeron, A. Garsia, M. Haiman, G. Tesler, Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods Appl. Anal. 6 (1999) 363–420] acting on the k-Schur functions [L. Lapointe, A. Lascoux, J. Morse, Tableaux atoms and a new Macdonald positivity conjecture, Duke Math. J. 116 (2003) 103–146; L. Lapointe, J. Morse, Schur functions analogs for a filtration of the symmetric functions space, J. Combin. Theory Ser. A 101 (2003) 191–224; L. Lapointe, J. Morse, Tableaux on k+1-cores, reduced words for affine permutations and k-Schur expansion, J. Combin. Theory Ser. A 112 (2005) 44–81] indexed by a single column has a coefficient in the expansion which is an analogue of the (q,t)-Catalan number with a level k. When k divides n we conjecture a representation theoretical model in this case such that the graded dimensions of the module are the coefficients of the (q,t)-Catalan polynomials of level k. When the parameter t is set to 1, the Catalan numbers of level k are shown to count the number of Dyck paths that lie below a certain Dyck path with q counting the area of the path.     

The limiting case of Haglund's (q,t)-Schröder theorem and an involution formula

As a generalization of Haglund's statistic on Dyck paths [Conjectured statistics for the q,t-Catalan numbers, Adv. Math. 175 (2) (2003) 319–334; A positivity result in the theory of Macdonald polynomials, Proc. Nat. Acad. Sci. 98 (2001) 4313–4316], Egge et al. introduced the (q,t)-Schröder polynomial S_n,d(q,t), which evaluates to the Schröder number when q=t=1 [A Schröder generalization of Haglund's statistic on Catalan paths, Electron. J. Combin. 10 (2003) 21pp (Research Paper 16, electronic)]. In their paper, S_n,d(q,t) was conjectured to be equal to the coefficient of a hook shape on the Schur function expansion of the symmetric function e_n, which Haiman [Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002) 371–407] has shown to have a representation-theoretic interpretation. This conjecture was recently proved by Haglund [A proof of the q,t-Schröder conjecture, Internat. Math. Res. Not. (11) (2004) 525–560]. However, because that proof makes heavy use of symmetric function identities and plethystic machinery, the combinatorics behind it is not understood. Therefore, it is worthwhile to study it combinatorially. This paper investigates the limiting case of the (q,t)-Schröder Theorem and obtains interesting results by looking at some special cases.     

Instance-optimality in probability with an -minimization decoder

Let Φ(ω), ωΩ, be a family of n×N random matrices whose entries _i,j are independent realizations of a symmetric, real random variable η with expectation and variance . Such matrices are used in compressed sensing to encode a vector by y=Φx. The information y holds about x is extracted by using a decoder . The most prominent decoder is the ℓ₁-minimization decoder Δ which gives for a given the element which has minimal ℓ₁-norm among all with Φz=y. This paper is interested in properties of the random family Φ(ω) which guarantee that the vector will with high probability approximate x in to an accuracy comparable with the best k-term error of approximation in for the range kan/log₂(N/n). This means that for the above range of k, for each signal , the vector satisfies

with high probability on the draw of Φ. Here, Σ_k consists of all vectors with at most k nonzero coordinates. The first result of this type was proved by Wojtaszczyk [P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math., in press] who showed this property when η is a normalized Gaussian random variable. We extend this property to more general random variables, including the particular case where η is the Bernoulli random variable which takes the values with equal probability. The proofs of our results use geometric mapping properties of such random matrices some of which were recently obtained in [A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005) 491–523].     

Interlacing and spacing properties of zeros of polynomials, in particular of orthogonal and -minimal polynomials,

Let be a sequence of polynomials with real coefficients such that uniformly for [α-δ,β+δ] with G(eⁱ)≠0 on [α,β], where 0α<βπ and δ>0. First it is shown that the zeros of are dense in [α,β], have spacing of precise order π/n and are interlacing with the zeros of p_n+1(cos) on [α,β] for every nn₀. Let be another sequence of real polynomials with uniformly on [α-δ,β+δ] and on [α,β]. It is demonstrated that for all sufficiently large n the zeros of p_n(cos) and strictly interlace on [α,β] if on [α,β]. If the last expression is zero then a weaker kind of interlacing holds. These interlacing properties of the zeros are new for orthogonal polynomials also. For instance, for large n a simple criteria for interlacing of zeros of Jacobi polynomials on [-1+,1-], >0, is obtained. Finally it is shown that the results hold for wide classes of weighted L_q-minimal polynomials, q[1,∞], linear combinations and products of orthogonal polynomials, etc.     

Kernel estimates and -spectral independence of generators of -semigroups

After the appearance of W. Arendt's result that “Gaussian estimate of a semigroup implies the L^p-spectral independence of the generator,” various generalizations have been obtained. This paper shows that a certain kernel estimate of a semigroup implies the L^p-spectral independence of the generator, generalizing the case of upper Gaussian estimate and “Gaussian estimate of order α(0,1] [S. Miyajima, H. Shindoh, Gaussian estimates of order α and L^p-spectral independence of generators of C₀-semigroups, Positivity 11 (1) (2007) 15–39], Definition 3.1.” The proof uses S. Karrmann's result about the L^p-spectral independence and B.A. Barnes' theorem about the spectrum of integral operators. As an application, the L^p-spectral independence of −[(−Δ)^α+V] (α(0,1]) for a suitable V is proved with the help of a recent result by V. Liskevich, H. Vogt and J. Voigt [V. Liskevich, H. Vogt, J. Voigt, Gaussian bounds for propagators perturbed by potentials, J. Funct. Anal. 238 (2006) 245–277].     

On the modulus of -convexity

In this paper, we prove that the moduli of W^*-convexity, introduced by Ji Gao [J. Gao, The W^*-convexity and normal structure in Banach spaces, Appl. Math. Lett. 17 (2004) 1381–1386], of a Banach space X and of the ultrapower of X itself coincide whenever X is super-reflexive. Moreover, we improve a sufficient condition for uniform normal structure of the space and its dual. This generalizes and strengthens the main results of [J. Gao, The W^*-convexity and normal structure in Banach spaces, Appl. Math. Lett. 17 (2004) 1381–1386].     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.     

Anti-periodic solutions for a class of nonlinear th-order differential equations with delays

In this paper, we use the Leray–Schauder degree theory to establish new results on the existence and uniqueness of anti-periodic solutions for a class of nonlinear nth-order differential equations with delays of the form

x⁽ⁿ⁾(t)+f(t,x⁽ⁿ⁻¹⁾(t))+g(t,x(t−τ(t)))=e(t).