Canonical Forms for Operation Tables of Finite Connected Quandles

We introduce a notion of natural orderings of elements of connected finite quandles. Let Q be such a quandle of order n. Any automophism on Q is a natural ordering when the elements are already ordered naturally. Suppose that the permutation *q is a cycle of length n ? 1. Then, the operation tables for such orderings coincide, which leads to the classification of automorphisms on Q. Moreover, every row and column of the operation table contains all the elements of such a quandle, which is due to K. Oshiro. We also consider the general case of finite connected quandles.     

S/P images of upper triangular M-matrices

Preconditioning by approximate factorizations is widely used in iterative methods for solving linear systems such as those arising from the finite element formulation of many engineering problems. The influence of the ordering of the unknowns on their convergence behaviour has been the subject of recent investigations because of its particular relevance for the parallel implementation of these methods. Consistent orderings are attractive for parallel implementations and subclasses of these orderings have been shown to also enhance the convergence properties of the associated preconditioned iteration scheme. The present contribution is concerned with one such class of orderings, called S/P consistent orderings. More precisely, we review here their known properties and we propose a new definition which enlarges their scope of application. A device, called S/P image of an upper triangular M-matrix, provides a criterion for checking S/P consistency and a means to compute a relevant parameter, called maximal reduction ratio. All known properties of S/P consistent orderings are generalized to the new definition.     

On a Class of Lattice Ordered Inverse Semigroups

It is well known that the free group on a non-empty set can be totally ordered and, further, that each compatible latttice ordering on a free group is a total ordering. On the other hand, Saitô has shown that no non-trivial free inverse semigroup can be totally ordered. In this note we show, however, that every free inverse monoid admits compatible lattice orderings which are closely related to the total orderings on free groups.These orderings are natural in the sense that the imposed partial ordering on the idempotents coincides with the natural partial ordering. For this to happen in a lattice ordered inverse semigroup, the idempotents must form a distributive lattice. The method of construction of the lattice orderings on free inverse monoids can be applied to show that naturally lattice ordered inverse semigroups with a given distributive lattice E of idempotents can have arbitrary Green's relation structure. Analogous results hold for naturally -semilatticed inverse semigroups. In this case, there is no restriction on the semilattice E of idempotents.We also show that every compatible lattice ordering on the free monogenic inverse monoid is of the type considered here. This permits us to prove that there are precisely eight distinct compatible lattice orderings on this semigroup. They belong to two families, each of which contains four members, of conjuguate lattice orderings.     

On the discrepancy of 3 permutations

Consider different orderings of an n-element set and the hypergraph consisting of the intervals of these orderings. A conjecture of J. Beck states that in the case of three orderings this hypergraph has bounded discrepancy. We show that for any constant number of orderings the discrepancy is O(log n). the proof also gives an efficient algorithm to determine such a coloring.     

Representation of preference orderings on Lp -spaces by integral functionals: discounting,continuity and TAS utility

This paper presents an axiomatic approach in a continuous time framework for representing preference orderings on L^p -spaces in terms of integral functionals. We show that if preference orderings on L^p -spaces satisfy continuity, separability, sensitivity, substitutability, additivity and lower boundedness, then there exists a utility function for the preference orderings such that the utility function is an integral functional with an upper semicontinuous integrand satisfying the growth condition. Moreover, if the preference orderings satisfy the continuity with respect to the weak topology of L^p -spaces, then the integrand is a concave integrand. As a result, time additive separable (TAS) utility functions with constant discount rates are obtained. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Domination Number of Certain Infinite Tournaments

We consider tournaments defined by several linear orderings of the vertex set according to some rule specifying the direction of each arc depending only on the order of the end vertices in each of the orderings. In the finite case, it was proved in Alon et al. (J Comb Theory Ser B 96:374–387, 2006) that the domination number of such tournaments is bounded in terms of the rule only. We show that for infinite tournaments, under some natural restrictions, the domination number is always finite, though in general cannot be bounded. We give some sufficient conditions under which there exists an upper bound in terms of the rule and/or the order types, and provide examples demonstrating that the bounds obtained are not very far from truth.     

Bounding derivation lengths with functions from the slow growing hierarchy

Let be a (finite) rewrite system over a (finite) signature. Let be a strict well-founded termination ordering on the set of terms in question so that the rules of are reducing under . Then is terminating. In this article it is proved for a certain class of far reaching termination orderings (of order type reaching up to the first subrecursively inaccessible ordinal, i.e. the proof-theoretic ordinal of ) that – under some reasonable assumptions which are met in current applications – the derivation lengths function for is bounded by a function from the slow growing hierarchy of level determined by the order type of the underlying termination ordering. This result is a (correction of the proof of and a) strong generalization of theorem 8.1 in Cichon's article Termination orderings and complexity characterisations. Leeds, Proof Theory 1990, (Aczel, Simmons, and Wainer, editors), Cambridge University Press 1992, 171-193. Received: 2 February 1996     

Countably categorical coloured linear orders

In this paper, we give a classification of (finite or countable) ?₀‐categorical coloured linear orders, generalizing Rosenstein's characterization of ?₀‐categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and ?_n‐combinations (for n ≥ 1). We give a method using coding trees to describe all structures in our list (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Towards an axiomatization of orderings

A set of six axioms for sets of relations is introduced. All well-known sets of specific orderings, such as linear and weak orderings, satisfy these axioms. These axioms impose criteria of closedness with respect to several operations, such as concatenation, substitution and restriction. For operational reasons and in order to link our results with the literature, it is shown that specific generalizations of the transitivity condition give rise to sets of relations which satisfy these axioms. Next we study minimal extensions of a given set of relations which satisfy the axioms. By this study we come to the fundamentals of orderings: They appear to be special arrangements of several types of disorder. Finally we notice that in this framework many new sets of relations have to be regarded as a set of orderings and that it is not evident how to minimize the number of these new sets of orderings.Symbol Table U universe (infinite countable) - D set of possible domains (finite and non-empty subsets of U) - R set of all considered relations - A empty relation on A - Id A identity relation on A - All A all relation on A - c complement operator (see Definition 2.1) - v converse operator (see Definition 2.1) - s symmetric part (see Definition 2.1) - asymmetric part (see Definition 2.1) - n non-diagonal part (see Definition 2.1) - r reflexive closure (see Definition 2.1) We gratefully acknowledge the support by the Co-operation Centre of Tilburg and Eindhoven Universities.     

Ramsey property, ultrametric spaces, finite posets, and universal minimal flows

We introduce the class COU _S of finite ultrametric spaces with distances in the set S and with two additional linear orderings. We also introduce the class EOP of finite posets with two additional linear orderings. In this paper, we prove that COU _S and EOP are Ramsey classes. In addition, we give an application of our results to calculus of universal minimal flows.     

Axiomatization of local-global principles for pp-formulas in spaces of orderings

We use a model theoretic approach to investigate properties of local-global principles for positive primitive formulas in spaces of orderings, such as the existence of bounds and the axiomatizability of local-global principles. As a consequence we obtain various classes of special groups satisfying local-global principles for all positive primitive formulas, and we show that local-global principles are preserved by some natural constructions in special groups.Mathematics Subject Classification (2000): 11E81, 03C65Acknowledgement This research was undertaken while both authors were partially suported by the European RTN Network (HPRN-CT-2001-00271) on real algebraic and analytic geometry.     

Relationships between pure tail orderings of lifetime distributions and some concepts of residual life

The concepts of pure-tail orderings as defined by sq- and D-orderings are shown to order the family of reliability life distributions which age smoothly in a natural way. This ordering extends to comparisons regarding the limiting behavior of the residual life, mean residual life, sojourn time between perfect repairs in repairable systems, failure rate and, through the preservation of sq- and D-orderings by various reliability operations, to certain coherent systems of components that age smoothly. Possible applications of the results to the industrial practice of cannibalization are also noted.     

Symmetrische Zerlegung von Kettenprodukten

A general theorem on the existence of partial matchings induced by linear orderings is proved which in the case of the natural orderings on the levels of a chainproduct yields full matchings and the symmetric decompositions of de Bruijn. In addition an explicit formula for these matchings is provided.     

Balancing poset extensions

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log₂ e (X) comparisons whereC is approximately 2.17.Supported in part by NSF Grant MCS83-01867.     

Linear orderings and the sets of periods for star maps

We show that Baldwin's characterization of the set of periods of continuous self maps of the n-star can be expressed in terms of a finite number of linear orderings.     

A criterion for the planarity of a graph

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244–271] has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion which, as well, is easily proved via Kuratowski's. The criterion is based on the observation that the imbedding of a graph in a plane imposes a cyclic ordering, say clockwise, on the edges incident with each vertex, and that these cyclic orderings are related.     

Linear Orderings of Low Degree

We consider the class of so-called k-quasidiscrete linear orderings, show that every k-quasi-discrete ordering of low degree has a computable representation, and study estimates for the complexity of all isomorphisms constructed in the article.     

Post hulls of spaces of signatures

We argue that Post hulls of spaces of signatures are a natural generalization of Boolean hulls of spaces of orderings.     

The absolute Galois group of a Hilbertian PRC field

We determine the absolute Galois group of a countable Hilbertian P (seudo) R(eal) C(losed) fieldP of characteristic 0. This group turns out to be real-free, determined up to isomorphism by the topological space of orderings ofP. Examples of such fieldsP are the proper finite extensions of the field of all totally real numbers. Part of this work was done while the authors were fellows of the Institute for Advanced Studies in Jerusalem Supported by NSA grant MDA 14776 and BSF grant 87-00038 Supported by NSA grant MDA 904-89-H-2028