A Loopless Algorithm for Generation of Basic Minimal Interval Orders

Erhlich introduced the concept of generating combinatorial structures in constant time per generated item. Such algorithms are called loopless and have been described for many objects. Myers introduced the idea of a basic minimal interval order. This paper presents a loopless algorithm for generating basic minimal interval orders.     

Basic Interval Orders

An interval order of length n has elements in correspondence with a collection of intervals in the linearly ordered set {1, 2, ..., n}. A basic interval order of length n has the property that removal of any element yields an order with length less than n. We construct and enumerate the set of basic length n interval orders.     

Shellability of Interval Orders

An finite interval order is a partially ordered set whose elements are in correspondence with a finite set of intervals in the line, with disjoint intervals being ordered by their relative position. We show that any such order is shellable in the sense that its (not necessarily pure) order complex is shellable.     

Counting Split Interval Orders

A poset (X,) is a split interval order (a.k.a. unit bitolerance order, proper bitolerance order) if a real interval and a distinguished point in that interval can be assigned to each xX so that xy precisely when x's distinguished point precedes y's interval, and x's interval precedes y's distinguished point. For each |X|9, we count the split interval orders and identify all posets that are minimal forbidden posets for split interval orders. The paper is a companion to Counting Split Semiorders by Fishburn and Reeds (this issue).     

Numerical Representations of Interval Orders

In the framework of the analysis of orderings whose associated indifference relation is not necessarily transitive, we study the structure of an interval order and its representability through a pair of real-valued functions. We obtain a list of characterizations of the existence of a representation, showing that the three main techniques that have been used in the literature to achieve numerical representations of interval orders are indeed equivalent.     

Enumeration of Mapping Classes for the Torus

We enumerate periodic, reducible, and Anosov elements of the mapping class group of the torus, and determine their growth function. Then we prove that almost all elements of the mapping class group of the torus are Anosov.     

Inductive Characterizations of Finite Interval Orders and Semiorders

We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class.     

Interval Extensions of Orders and Temporal Approximation Spaces

Siberian Mathematical Journal - Studying the algorithmic properties of interval extensions of dense linear orders, in particular, the complexity degrees (namely, the $ sSigma $ -degree)...     

Unit Interval Orders of Open and Closed Intervals

A poset P = (X, ?) is a unit OC interval order if there exists a representation that assigns an open or closed real interval I(x) of unit length to each x ∈ P so that x ? y in P precisely when each point of I (x) is less than each point in I (y). In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The algorithm takes a poset P as input and either produces a representation or returns a forbidden poset induced in P.     

On-line Chain Partitioning of Up-growing Interval Orders

On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses chains to cover poset of width w. Felsner (Theor. Comput. Sci., 175(2):283–292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using chains for width w posets and proved that his solution is optimal. In this paper, we study on-line chain partitioning of up-growing interval orders. We prove lower bound and upper bound to be 2w−1 for width w posets. Piotr Micek and Bartłomiej Bosek are scholars of the project which is co-financed from the European Social Fund and national budget in the frame of The Integrated Regional Operational Programme.     

A Genesis of Interval Orders and Semiorders: Transitive NaP-preferences

A NaP-preference (necessary and possible preference) on a set A is a pair \({\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}\) of binary relations on A such that its necessary component \({\succsim^{^{_N}} \!\!}\) is a partial preorder, its possible component \({\succsim^{^{_P}} \!\!}\) is a completion of \({\succsim^{^{_N}} \!\!}\) , and the two components jointly satisfy natural forms of mixed completeness and mixed transitivity. We study additional mixed transitivity properties of a NaP-preference \({\left(\succsim^{^{_N}}\!,\,\succsim^{^{_P}}\!\right)}\) , which culminate in the full transitivity of its possible component \({\succsim^{^{_P}} \!\!}\) . Interval orders and semiorders are strictly related to these properties, since they are the possible components of suitably transitive NaP-preferences. Further, we introduce strong versions of interval orders and semiorders, which are characterized by enhanced forms of mixed transitivity, and use a geometric approach to compare them to other well known preference relations.     

Enumeration, Construction and Random Generation of Block Codes

We discuss some methods for the enumeration, construction and random generation of isometry classes of block codes using methods from algebraic combinatorics.     

两类重要p-群及其自同构群的阶

In the paper we obtain two infinite classes of p-groups,calculate the orders of their automorphism groups and correct a mistake(perhaps misprinted)of Rodney James'paper in 1980.     

Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices

We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known:(1) The bijection between maximal chains in the antichain lattice A(P) and the linear extensions of P.(2) The bijection between maximal chains in the lattice of maximal antichains A_M(P) and minimal interval extensions of P.We discuss two approaches to associate interval orders with chains in A(P). This leads to new bijections generalizing Bijections 1 and 2. As a consequence, we characterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P.Seeking for a way of representing interval reductions of P by chains we came upon the separation lattice S(P). Chains in this lattice encode an interesting subclass of interval reductions of P. Let S_M(P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations, the above bijection specializes to a bijection which nicely complements 1 and 2.(3) A bijection between maximal chains in the lattice of maximal separations S_M(P) and minimal interval reductions of P.     

The Number of Isomorphism Classes of Finite Groups with Given Element Orders

Let G be a finite group and _e(G) the set of element orders of G. Denote by h( _e(G)) the number of isomorphism classes of finite groups H satisfying _e(H) = _e(G). We prove that if G has at least three prime graph components, then h( _e (G)){1, }.     

Approximation Properties and Some Classes of Operators

The following questions and close problems are studied.(i) Is it true that T is p-nuclear provided that T ^** is p-nuclear? (ii) Is it true that Tis dually p-nuclear provided that T ^* is p-nuclear? (iii) Is it true that if T ^*is compactly factorable in the space l _p, then T is (strictly) factorable in the space l _p'? Here, T ^* is the adjoint operator of a bounded operator T:X Yin Banach spaces X and Y. Bibliography: 30 titles.     

关于群类的Sylow性质

群类理论是在有限可解群研究工作的基础上发展起来的,但近年来对有限群论的许多方面都起到越来越大的作用.在考察群类性质时,注意到一个Fitting类(?)在可解群G中的(?)内射子具有Sylow子群所具有的某些性质,并且关于Sylow定理中(Sy13),证明了对于群的本原子群,成立更强的结论.     

Some Classes of Nilpotent Associative Algebras

We further the study of rings with no middle class by focusing on an interpretation of that property in terms of the lattice of hereditary pretorsion classes over a given ring. For non-semisimple rings, the absence of a middle class is equivalent to the requirement that the class of all semisimple right modules be a coatom in that lattice. Taking advantage of this perspective, we discover new facts and shed light on others already known with a possibly more direct interpretation without having to refer to an exhaustive analysis of the structure theorems available in the literature. Our approach also allows us to characterize rings with no middle class in terms of hereditary pretorsion classes containing the class of all singular right modules. We discuss the open problem of whether there is a ring with no right middle class which is not right Noetherian and see, in particular, that an indecomposable ring satisfying that property would have to be Morita equivalent to a certain type of subring of a full linear ring.     

On the Orders of Nonlinear Approximations for Classes of Functions of Given Form

Suppose that Δ ₊ ^s is the set of functions x: I → ℝ on a finite interval I such that the divided differences [x; t ₀,..., t _s ] of order _s ∈ ℕ of these functions are nonnegative for all collections from (s +1) different points t ₀,..., t _s ∈ I. For all s ∈ ℕ and 1 ≤ p ≤ ∞, we establish exact orders of best approximations by splines with free nodes and rational functions in the metrics of L _p for classes , where B _p is the unit ball in L _p . We also establish the asymptotics of pseudodimensional widths in L _p of these classes of functions.__________Translated from Matematicheskie Zametki, vol. 78, no. 1, 2005, pp. 98–114.Original Russian Text Copyright © 2005 by V. N. Konovalov.