On the Fixed Point Property for (3 + 1)-Free Ordered Sets

We prove that if a finite (3 + 1)-free ordered set of height two has the fixed point property, then it is dismantlable by irreducibles. We provide an example of a finite (3 + 1)-free ordered set of height three with the fixed point property and no irreducible elements. We characterize the minimal automorphic ordered sets which are respectively (3 + 1)-free, (2 + 2)-free and N-free.     

Varieties of two-dimensional cylindric algebras.¶Part I: Diagonal-free case

We investigate the lattice of all subvarieties of the variety Df ₂ of two-dimensional diagonal-free cylindric algebras. We prove that a Df ₂-algebra is finitely representable if it is finitely approximable, characterize finite projective Df ₂-algebras, and show that there are no non-trivial injectives and absolute retracts in Df ₂. We prove that every proper subvariety of Df ₂ is locally finite, and hence Df ₂ is hereditarily finitely approximable. We describe all six critical varieties in , which leads to a characterization of finitely generated subvarieties of Df ₂. Finally, we describe all square representable and rectangularly representable subvarieties of Df ₂. Received May 25, 2000; accepted in final form November 2, 2001.     

Homomorphisms into N *

We study the properties of continuous homomorphisms from β S into N ^* and from N ^* into N ^* . We show that the image C of N ^* under a continuous homomorphism which does not arise from the continuous extension of a homomorphism mapping N to itself, has the property that C+C is a singleton.     

Approach Theory in Merotopic, Cauchy and Convergence Spaces. I

We introduce the notions of approach-merotopic structure and approach-filter merotopic structure by means of a map assigning to a collection of sets 'smallness' of members and define categories AMER and AFIL containing MER and FIL as bireflectively and bicoreflectively embedded subcategories, respectively. We show that the category AMER is a topological construct and AFIL which is a supercategory of ps-MET as well is a cartesian closed topological category bicoreflectively embedded in AMER.     

A Criterion for Projective Modules

In case G is a finite group, there is a well-known criterion for projective modules: A ? G-module M is projective if and only if it is ? -free and has finite projective dimension. We first investigate whether only finite groups satisfy the above criterion. In the class of groups L H 𝔉, we conclude that this is true. Secondly, we consider the problem when a stably flat Γ-module is projective, where Γ is an arbitrary group. We show that if Γ is an L H 𝔉-group, then every stably flat cofibrant ? Γ-module is projective.     

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than \(n=500\). This translates to a semidefinite constraint of order 250, 000 and \(625\times 10^8\) nonnegative constrained variables, before applying the reduction techniques.

     

Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being NP\boldsymbol{\mathit{NP}}-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.     

Extended neighborhood: Definition and characterization

We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a Neighborhood for combinatorial optimization problem X. We say that N is LO-equivalent (locally optimal) to N if for any instance of X, the set of locally optimal solutions with respect to N and N are the same. The union of two LO-equivalent neighborhoods is itself LO-equivalent to the neighborhoods. The largest neighborhood that is LO-equivalent to N is called the extended neighborhood of N, and denoted as N^*. We analyze some basic properties of the extended neighborhood. We provide a geometric characterization of the extended neighborhood N^* when the instances have linear costs defined over a cone. For the TSP, we consider 2-opt^*, the extended neighborhood for the 2-opt (i.e., 2-exchange) neighborhood structure. We show that number of neighbors of each tour T in 2-opt^* is at least (n /2 -2)!. We show that finding the best tour in the 2-opt^* neighborhood is NP-hard. We also show that the extended neighborhood for the graph partition problem is the same as the original neighborhood, regardless of the neighborhood defined. This result extends to the quadratic assignment problem as well. This result on extended neighborhoods relies on a proof that the convex hull of solutions for the graph partition problem has a diameter of 1, that is, every two corner points of this polytope are adjacent.Acknowledgement We thank Ravi Ahuja, Andreas Schulz, and Ozlem Ergun for useful discussions. This research was supported through NSF contract DMI-9820998.     

On relative enumerability of Turing degrees

Let d be a Turing degree, R[d] and Q[d] denote respectively classes of recursively enumerable (r.e.) and all degrees in which d is relatively enumerable. We proved in Ishmukhametov [1999] that there is a degree d containing differences of r.e.sets (briefly, d.r.e.degree) such that R[d] possess a least elementm 0. Now we show the existence of a d.r.e. d such that R[d] has no a least element. We prove also that for any REA-degree d below 0 the class Q[d] cannot have a least element and more generally is not bounded below by a non-zero degree, except in the trivial cases. Received: 17 January 1996     

On the group extension of the transformation associated to non-archimedean continued fractions

Summary Let F_q be a finite field with q elements. We consider formal Laurent series of F_q -coefficients with their continued fraction expansions by F_q -polynomials. We prove some arithmetic properties for almost every formal Laurent series with respect to the Haar measure. We construct a group extension of the non-archimedean continued fraction transformation and show its ergodicity. Then we get some results as an application of the individual ergodic theorem. We also discuss the convergence rate for limit behaviors.     

Membership of A ∨ G for classes of finite weakly abundant semigroups

We consider the question of membership of A ∨ G, where A and G are the pseudovarieties of finite aperiodic semigroups, and finite groups, respectively. We find a straightforward criterion for a semigroup S lying in a class of finite semigroups that are weakly abundant, to be in A ∨ G. The class of weakly abundant semigroups contains the class of regular semigroups, but is much more extensive; we remark that any finite monoid with semilattice of idempotents is weakly abundant. To study such semigroups we develop a number of techniques that may be of interest in their own right.     

Change of generalized indices of stationary solutions. to multiparametric optimization

We study the local change of the generalized index, which is a modification of the Morse index and the stationary index, for the multiparametric optimization. Under the Regular Value Condition, the change of the generalized index around a triplet (x,v,t) is locally bounded by the dimension of the parameter vector t, where x is a variable vector and v a vector of the Lagrange multiplier space. We also discuss the local change of the generalized index around a pair (x,t). Received: March 27, 1998 / Accepted: January 29, 2000?Published online April 20, 2000     

Semi-self-decomposable distributions on Z<Subscript>+</Subscript>

We present a notion of semi-self-decomposability for distributions with support in Z ₊. We show that discrete semi-self-decomposable distributions are infinitely divisible and are characterized by the absolute monotonicity of a specific function. The class of discrete semi-self-decomposable distributions is shown to contain the discrete semistable distributions and the discrete geometric semistable distributions. We identify a proper subclass of semi-self-decomposable distributions that arise as weak limits of subsequences of binomially thinned sums of independent Z ₊-valued random variables. Multiple semi-self-decomposability on Z ₊ is also discussed.     

Spectral properties of k p schrödinger operators in one space dimension

In the physics of layered semiconductor devices the k · p method in combination with the envelope function approach is a well established tool for band structure calculations. We perform a rigorous mathematical analysis of spectral properties for the corresponding spatially one dimensional k · p Schrödinger operators;thereby encompassing a wide class of such operators. This class covers many of the k · p operators prevalent in solid state physics. It includes k · p Schrödinger operators with piecewise constant coefficients, a prerequisite for dealing with the important case of semiconductor hetero-structures. In particular, we address the question of persistence of a spectral gap over the wave vector range. We also introduce a regularization of the problem which gives rise to a consistent discretization of k · p operators with jumping coefficients and describe design patterns for the numerical treatment of k · p operators.     

A bilinear algorithm for sparse representations

We consider the following sparse representation problem: represent a given matrix X∈ℝ ^m×N as a multiplication X=AS of two matrices A∈ℝ ^m×n (m≤n<N) and S∈ℝ ^n×N , under requirements that all m×m submatrices of A are nonsingular, and S is sparse in sense that each column of S has at least n−m+1 zero elements. It is known that under some mild additional assumptions, such representation is unique, up to scaling and permutation of the rows of S. We show that finding A (which is the most difficult part of such representation) can be reduced to a hyperplane clustering problem. We present a bilinear algorithm for such clustering, which is robust to outliers. A computer simulation example is presented showing the robustness of our algorithm.     

Approach Theory in Merotopic, Cauchy and Convergence Spaces. II

We define the notions of approach-Cauchy structure and ultra approach-Cauchy structure. We study the categorical properties of ACHY and uACHY and show that in these schemes Cauchy spaces and extended pseudo-(ultra)metric spaces are regarded as entities of the same kind. Furthermore, we investigate the relation with convergence-approach spaces and obtain a relationship similar to that of CONV and CHY.     

The Tits–Kantor–Koecher Construction and Birepresentations of the Jordan Superpair SH(1, n)

Abstract

We introduce the concept of bimodule over a Jordan superpair and the Tits– Kantor–Koecher construction for bimodules. Using the construction we obtain the classification of irreducible bimodules over the Jordan superpair SH(1, n). We also prove semisimplicity for a class of finite dimensional SH(1, n)-bimodules for n ≥ 3.     

On Hereditary Coreflective Subcategories of Top

Let A be a topological space which is not finitely generated and CH(A) denote the coreflective hull of A in Top. We construct a generator of the coreflective subcategory SCH(A) consisting of all subspaces of spaces from CH(A) which is a prime space and has the same cardinality as A. We also show that if A and B are coreflective subcategories of Top such that the hereditary coreflective kernel of each of them is the subcategory FG of all finitely generated spaces, then the hereditary coreflective kernel of their join CH(AB) is again FG.     

Solving Chisini’s functional equation

We investigate the n-variable real functions G that are solutions of the Chisini functional equation F(x) = F(G(x), . . . , G(x)), where F is a given function of n real variables. We provide necessary and sufficient conditions on F for the existence and uniqueness of solutions. When F is nondecreasing in each variable, we show in a constructive way that if a solution exists then a nondecreasing and idempotent solution always exists. We also provide necessary and sufficient conditions on F for the existence of continuous solutions and we show how to construct such a solution. We finally discuss a few applications of these results.