Generation and Enumeration of Some Classes of Interval Orders

In this paper we consider the class of interval orders, recently considered by several authors from both an algebraic and an enumerative point of view. According to Fishburn’s Theorem (Fishburn J Math Psychol 7:144–149, 1970), these objects can be characterized as posets avoiding the poset 2?+?2. We provide a recursive method for the unique generation of interval orders of size n?+?1 from those of size n, extending the technique presented by El-Zahar (1989) and then re-obtain the enumeration of this class, as done in Bousquet-Melou et al. (2010). As a consequence we provide a method for the enumeration of several subclasses of interval orders, namely AV(2?+?2, N), AV(2?+?2, 3?+?1), AV(2?+?2, N, 3?+?1). In particular, we prove that the first two classes are enumerated by the sequence of Catalan numbers, and we establish a bijection between the two classes, based on the cardinalities of the principal ideals of the posets.     

Monadic MV-algebras I: a study of subvarieties

In this paper, we study and classify some important subvarieties of the variety of monadic MV-algebras. We introduce the notion of width of a monadic MV-algebra and we prove that the equational class of monadic MV-algebras of finite width k is generated by the monadic MV-algebra [0, 1] ^k . We describe completely the lattice of subvarieties of the subvariety ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ generated by [0, 1] ^k . We prove that the subvariety generated by a subdirectly irreducible monadic MV-algebra of finite width depends on the order and rank of ?A, the partition associated to A of the set of coatoms of the boolean subalgebra B(A) of its complemented elements, and the width of the algebra. We also give an equational basis for each proper subvariety in ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ . Finally, we give some results about subvarieties of infinite width.     

Additive operators preserving rank-additivity on symmetry matrix spaces

We characterize the additive operators preserving rank-additivity on symmetry matrix spaces. LetS _n(F) be the space of alln×n symmetry matrices over a fieldF with 2,3 ∈F ^*, thenT is an additive injective operator preserving rank-additivity onS _n(F) if and only if there exists an invertible matrixU∈M _n(F) and an injective field homomorphism ? ofF to itself such thatT(X)=cUX ^?U^T, ?X=(x_ij)∈S_n(F) wherec∈F ^*,X ^?=(?(x _ij)). As applications, we determine the additive operators preserving minus-order onS _n(F) over the fieldF.     

On diversity and stability of unit bases for the Euclidean metric

We prove the existence of a family Ω(n) of 2 ^c (where c is the cardinality of the continuum) subgraphs of the unit distance graph (E ⁿ , 1) of the Euclidean space E ⁿ , n ≥ 2, such that (a) for each graph G ? Ω(n), any homomorphism of G to (E ⁿ , 1) is an isometry of E ⁿ ; moreover, for each subgraph G ₀ of the graph G obtained from G by deleting less than c vertices, less than c stars, and less than c edges (we call such a subgraph reduced), any homomorphism of G ₀ to (E ⁿ , 1) is an isometry (of the set of the vertices of G ₀); (b) each graph G ? Ω(n) cannot be homomorphically mapped to any other graph of the family Ω(n), and the same is true for each reduced subgraph of G.     

Distance regularity of Kerdock codes

A code is called distance regular, if for every two codewords x, y and integers i, j the number of codewords z such that d(x, z) = i and d(y, z) = j, with d the Hamming distance, does not depend on the choice of x, y and depends only on d(x, y) and i, j. Using some properties of the discrete Fourier transform we give a new combinatorial proof of the distance regularity of an arbitrary Kerdock code. We also calculate the parameters of the distance regularity of a Kerdock code.     

Conic volume ratio of the packing cone associate to a convex body

Given a convex body ${K\subset\mathbb{R}^n}$ (n??? 1) which contains o in its interior and ${{\bf u} \in S^{n-1}}$ , we introduce conic volume ratio r(K, u) of K in the direction of u by $$r(K, {\bf u})=\frac{vol(cone(K,{\bf u})\cap B_2^n)}{vol(B_2^n)},$$ where cone(K, u) is the packing cone of K in the direction of u. We prove that if K is an o-symmetric convex body in ${\mathbb{R}^n}$ and r(K, u) is a constant function of u, then K must be a Euclidean ball.     

A homogeneous smoothing-type algorithm for symmetric cone linear programs

In this paper, we investigate a smoothing-type algorithm for solving the symmetric cone linear program （（SCLP） for short） by making use of an augmented system of its optimality conditions. The algorithm only needs to solve one system of linear equations and to perform one line search at each iteration. It is proved that the algorithm is globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, the algorithm may correctly detect solvability of （SCLP）. Furthermore, if （SCLP） has a solution, then the algorithm will generate a solution of （SCLP）, and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of （SCLP）.     

Existence and nonuniqueness of solutions to a functional-differential equation

We examine the functional-differential equation Δu(x) — div(u(H(x))f (x)) = 0 on a torus which is a generalization of the stationary Fokker-Planck equation. Under sufficiently general assumptions on the vector field f and the map H, we prove the existence of a nontrivial solution. In some cases the subspace of solutions is established to be multidimensional.     

Reflexive relations on algebras with Boolean lattice reducts

For any algebra A, let Ref(A) be the algebra of compatible reflexive binary relations on A under intersection, composition, and converse with the universal and identity relations as constants. We characterize all Ref(A) where A is a finite algebra with a Boolean lattice reduct.     

Comparing Invariants of SK1

In this text, we compare an invariant of the reduced Whitehead group SK ₁ of a central simple algebra recently introduced by Kahn (2010) to other invariants of SK ₁. Doing so, we prove the non-triviality of Kahn’s invariant using the non-triviality of an invariant introduced by Suslin (1991) which is non-trivial for Platonov’s examples of non-trivial SK ₁ (Platonov, Math USSR Izv 10(2):211–243, 1976). We also give a formula for the value on the centre of the tensor product of two symbol algebras which generalises a formula of Merkurjev for biquaternion algebras (Merkurjev 1995).     

On rings whose number of centralizers of ideals is finite

LetR be a ring. For the setF of all nonzero ideals ofR, we introduce an equivalence relation inF as follows: For idealsI andJ, I～J if and only ifV _R (I)=V _R(J), whereV _R() is the centralizer inR. LetI _R=F/～. Then we can see thatn(I _R), the cardinality ofI _R, is 1 if and only ifR is either a prime ring or a commutative ring (Theorem 1.1). An idealI ofR is said to be a commutator ideal ifI is generated by{st?ts; s∈S, t∈T} for subsetS andT ofR, andR is said to be a ring with (N) if any commutator ideal contains no nonzero nilpotent ideals. Then we have the following main theorem: LetR be a ring with (N). Thenn(I _R) is finite if and only ifR is isomorphic to an irredundant subdirect sum ofS⊕Z whereS is a finite direct sum of non commutative prime rings andZ is a commutative ring (Theorem 2.1). Finally, we show that the existence of a ringR such thatn(I _R)=m for any given natural numberm.     

Boolean topological graphs of semigroups: the lack of first-order axiomatization

The graph of an algebra A is the relational structure G(A) in which the relations are the graphs of the basic operations of A. For a class ?? of algebras let G(??)={G(A)∣A∈??}. Assume that ?? is a class of semigroups possessing a nontrivial member with a neutral element and let ? be the universal Horn class generated by G(??). We prove that the Boolean core of ?, i.e., the topological prevariety generated by finite members of ? equipped with the discrete topology, does not admit a first-order axiomatization relative to the class of all Boolean topological structures in the language of ?. We derive analogous results when ?? is a class of monoids or groups with a nontrivial member.     

Multipoint matrix Padé approximant bounds on effective anisotropic transport coefficients of two-phase media

It is well known that a tensor Stieltjes function f represents an effective transport coefficient q of an inhomogeneous medium consisting of two isotropic components. In this paper, we investigate multipoint matrix Padé approximants to matrix expansions of f. We prove that matrix Padé ones to f estimate f from the top and below. Consequently the Padé approximants to q form upper and lower bounds on q. The inequalities for matrix Padé bounds on f and q are established. They reduce to the inequalities for scalar Padé ones Tokarzewski (ZAMP 61:773–780, 2010). As an illustrative example, matrix Padé estimates of an effective conductivity of a specially laminated two-phase medium are computed.     

Z-transformations on proper and symmetric cones

Motivated by the similarities between the properties of Z-matrices on $R^{n}_+$ and Lyapunov and Stein transformations on the semidefinite cone $\mathcal {S}^n_+$ , we introduce and study Z-transformations on proper cones. We show that many properties of Z-matrices extend to Z-transformations. We describe the diagonal stability of such a transformation on a symmetric cone by means of quadratic representations. Finally, we study the equivalence of Q and P properties of Z-transformations on symmetric cones. In particular, we prove such an equivalence on the Lorentz cone.     

Analysis of Basis Pursuit via Capacity Sets

Finding the sparsest solution α for an under-determined linear system of equations D α=s is of interest in many applications. This problem is known to be NP-hard. Recent work studied conditions on the support size of α that allow its recovery using ? ₁-minimization, via the Basis Pursuit algorithm. These conditions are often relying on a scalar property of D called the mutual-coherence. In this work we introduce an alternative set of features of an arbitrarily given D, called the capacity sets. We show how those could be used to analyze the performance of the basis pursuit, leading to improved bounds and predictions of performance. Both theoretical and numerical methods are presented, all using the capacity values, and shown to lead to improved assessments of the basis pursuit success in finding the sparest solution of D α=s.     

Euler method vs. GESS method for dynamical systems

In this paper we introduce GESS method and show that dynamics of the systemy′ =A(s,t,y)y is more faithfully approximated by GESS method than by Euler method. Numerical experiments are given for the comparison of GESS method with Euler method.     

AnO(\sqrt n L) iteration potential reduction algorithm for linear complementarity problems

This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an (x, y)∈? ²ⁿ such thaty=Mx+q, (x,y)?0 andx ^T y=0. The algorithm reduces the potential function $$f(x,y) = (n + \sqrt n )\log x^T y - \sum\limits_{i = 1}^n {\log x_i y_i } $$ by at least 0.2 in each iteration requiring O(n ³) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by \(O(\sqrt n L)\) , it generates, in at most \(O(\sqrt n L)\) iterations, an approximate solution with the potential function value \( - O(\sqrt n L)\) , from which we can compute an exact solution in O(n ³) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.     

MV-closures of Wajsberg hoops and applications

In this paper we construct, given a Wajsberg hoop A, an MV-algebra MV(A) such that the underlying set A of A is a maximal filter of MV(A) and the quotient MV(A)/A is the two element chain. As an application we provide a topological duality for locally finite Wajsberg hoops based on a previously known duality for locally finite MV-algebras. We also give another duality for k-valued Wajsberg hoops based on a different representation of k-valued MV-algebras and show the relation to the first duality. We also apply this construction to give a topological representation for free k-valued Wajsberg hoops.     

De Vries Algebras and Compact Regular Frames

By the de Vries theorem, the category DeV of de Vries algebras is dually equivalent to the category KHaus of compact Hausdorff spaces. By the Isbell theorem, the category KRFrm of compact regular frames is dually equivalent to KHaus. The proofs of both theorems employ the axiom of choice. It is a consequence of the de Vries and Isbell theorems that DeV is equivalent to KRFrm. We give a direct proof of this result, which is choice-free. In the absence of the axiom of countable dependent choice (CDC), the category KCRFrm of compact completely regular frames is a proper subcategory of KRFrm. We introduce the category cDeV of completely regular de Vries algebras, which in the absence of (CDC) is a proper subcategory of DeV, and show that cDeV is equivalent to KCRFrm. Finally, we show how the restriction of the equivalence of DeV and KRFrm works in the zero-dimensional and extremally disconnected cases.     

Difference Sets in {\mathbb{Z}}_4^m and {\mathbb{F}}_2^{2m}

Let R=GR(4,m) be the Galois ring of cardinality 4^m and let T be the Teichmüller system of R. For every map λ of T into { -1,+1} and for every permutation Π of T, we define a map φ _λ ^Π of Rinto { -1,+1} as follows: if x∈R and if x=a+2b is the 2-adic representation of x with x∈T and b∈T, then φ _λ ^Π (x)=λ(a)+2Tr(Π(a)b), where Tr is the trace function of R . For i=1 or i=-1, define D _i as the set of x in R such thatφ _λ ^Π =i. We prove the following results: 1) D _i is a Hadamard difference set of (R,+). 2) If φ is the Gray map of R into ${\mathbb{F}}_2^{2m}$ , then (D _i) is a difference set of ${\mathbb{F}}_2^{2m}$ . 3) The set of D _i and the set of φ(D _i) obtained for all maps λ and Π, both are one-to-one image of the set of binary Maiorana-McFarland difference sets in a simple way. We also prove that special multiplicative subgroups of R are difference sets of kind D _i in the additive group of R. Examples are given by means of morphisms and norm in R.