Cyclic orders: Equivalence and duality

Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomassé’s recent proof of Gallai’s conjecture. We explore this notion further: we prove that two cyclic orders are equivalent if and only if the winding number of every circuit is the same in the two. The proof is short and provides a good characterization and a polynomial algorithm for deciding whether two orders are equivalent. We then derive short proofs of Gallai’s conjecture and a theorem “polar to” the main result of Bessy and Thomassé, using the duality theorem of linear programming, total unimodularity, and the new result on the equivalence of cyclic orders.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

An Extension Result for Continuous Valuations

It is shown, by a simple and direct proof, that if a boundedvaluation on a monotone convergence space is the supremum ofa directed family of simple valuations, then it has a uniqueextension to a Borel measure. In particular, this holds forany directed complete partial order with the Scott topology.It follows that every bounded and continuous valuation on acontinuous directed complete partial order can be extended uniquelyto a Borel measure. The last result also holds for -finite valuations,but fails for directed complete partial orders in general.     

On a Strong Continuous Analogue of the Szpilrajn Theorem and its Strengthening by Dushnik and Miller

The Szpilrajn theorem states that every (partial) order has a total (linear) refinement or extension by a total (linear) order. Its strengthening by Dushnik and Miller states, moreover, that every (partial) order is the intersection of its total (linear) refinements or extensions. In any theory that combines the concepts of topology and order, however, one is interested in (weakly) continuous orders. Therefore, in this paper the question will be answered, if the Szpilrajn theorem and its strengthening by Dushnik and Miller respectively can be generalized in such a way that they also include the case that (weakly) continuous orders are considered. Since arbitrary preorders are not considered in this paper we speak of possible strong continuous analogues of the Szpilrajn theorem and its strengthening by Dushnik and Miller. The main results of this paper show that the Dushnik–Miller theorem cannot be generalized to the (weakly) continuous case while the Szpilrajn theorem at least in very particular situations allows generalizations to the case that (weakly) continuous orders are considered. Finally, also a strong semicontinuous analogue of the Szpilrajn theorem and its strengthening by Dushnik and Miller will be discussed.     

VC-Dimension of Sets of Permutations

VC-dimension of a set of permutations to be the maximal k such that there exist distinct that appear in A in all possible linear orders, that is, every linear order of is equivalent to the standard order of for at least one permutation . In other words, the VC-dimension of A is the maximal k such that for some the restriction of A to contains all possible linear orders. This is analogous to the VC-dimension of a set of strings. Our main result is that there exists a universal constant C such that any set of permutations with VC-dimension 2 is of size . This is analogous to Sauer's lemma for the case of VC-dimension 2. One corollary of our main result is that any acyclic set of linear orders of is of size , (a set A of linear orders on is called acyclic if no 3 elements appear in A in all 3 orders (i,j,k), (k,i,j) and (j,k,i)). The size of the largest acyclic set of linear orders has interested researchers for many years because it is the largest number of linear orders of n alternatives such that the following is always satisfied: if each one of a set of voters chooses one of these orders as his preference then the majority relation between each two alternatives is transitive. Received August 6, 1998     

A non-inversion theorem for the jump operator

R.W. Robinson's [15] interpolation theorem shows that the Sacks [16] jump inversion theorem can be extended to invert the jump and preserve order on any finite linearly ordered set of degrees r.e. in and above (REA in) 0′. We show that although the Friedberg inversion theorem can be extended to partial orders, the Sacks theorem cannot be extended to even the simplest ones even if we allow the inversion to carry us into rather than just the r.e. degrees. This strong non-inversion theorem also decides the problem that Lerman [12] has called the main obstacle to deciding the theory of the degrees with jump. It is a corollary to our main result:

Theorem 1.1. There are a₀ and a₁ REA in 0′ such that a₀ a₁<0” and if u<0′, then not both a₀ and a₁ are r.e. in u.

Other corollaries include a solution to a problem suggested by Jockusch and Soare: not every a REA in 0′ is the jump of a degree which is half of an r.e. minimal pair. The proof introduces a new type of 0 priority argument in which the tree of strategies is ω+1 branching and so simply determining the true path requires a 0 oracle.     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

Links between associated additive Galois modules and computation of H for local formal group modules

Using the methods described in the papers (Documenta Math. 5 (2000) 657; Local Leopoldt's problem for ideals in p-extensions of complete discrete valuation fields, to appear), we prove that a cocycle for a formal group in a Galois p-extension of a complete discrete valuation field is a coboundary if and only if the corresponding group algebra elements increase valuations by a number that is sufficiently large. We also calculate the valuation of the splitting element of a coboundary. A special case of the main theorem allows us to determine when a p-extension of a complete discrete valuation fields contains a root of a Kummer equation for a formal group. The theorem of Coates-Greenberg for formal group modules in deeply ramified extensions is generalized to noncommutative formal groups. Some results concerning finite torsion modules for formal groups are obtained.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

An Intuitionistic Axiomatisation of Real Closed Fields

We give an intuitionistic axiomatisation of real closed fields which has the constructive reals as a model. The main result is that this axiomatisation together with just the decidability of the order relation gives the classical theory of real closed fields. To establish this we rely on the quantifier elimination theorem for real closed fields due to Tarski, and a conservation theorem of classical logic over intuitionistic logic for geometric theories.     

Cohomology equations near hyperbolic points and geometric versions of sternberg linearization theorem

We prove that if two germs of diffeomorphisms preserving a voiume, symplectic, or contact structure are tangent to a high enough order and the linearization is hyperbolic, it is possible to find a smooth change of variables that sends one into the other and which, moreover, preserves the same geometric structure. This result is a geometric version of Sternberg’s linearization theorem, which we recover as a particular case. An analogous result is also proved for flows.     

Sorting orders,subword complexes,Bruhat order and total positivity

In this note we construct a poset map from a Boolean algebra to the Bruhat order which unveils an interesting connection between subword complexes, sorting orders, and certain totally nonnegative spaces. This relationship gives a simple new proof that the proper part of Bruhat order is homotopy equivalent to the proper part of a Boolean algebra — that is, to a sphere. We also obtain a geometric interpretation for sorting orders. We conclude with two new results: that the intersection of all sorting orders is the weak order, and the union of sorting orders is the Bruhat order.     

Angle orders

A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281.     

Extendability of Cyclic Orders

A cyclic order is a ternary relation that satisfies ternary transitivity and asymmetry conditions. Such a ternary relation is extendable if it is included in a complete cyclic order on the same ground set. Unlike the case of linear extensions of partial orders, a cyclic order need not be extendable. The extension problem for cyclic orders is to determine if a cyclic order is extendable. This problem is known to be NP-complete. We introduce a class of cyclic orders in which the extension problem can be solved in polynomial time. The class provides many explicit examples of nonextendable cyclic orders that were not previously known, including a nonextendable cyclic order on seven points. Let μ be the maximum cardinality of a ground set on which all cyclic orders are extendable. It has been shown that μ≤9. We prove that μ=6. This answers a question of Novák. In addition, we characterize the nonextendable cyclic orders on seven and eight points. Our results are intimately related to irreducible partially ordered set of order dimension three, and to fractional vertices of generalized transitive tournament polytopes. As by-products, we obtain a characterization of cyclically ordered sets of dimension two, and a new proof of a theorem of Dridi on small linear ordering polytopes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Geometric Bogomolov conjecture for abelian varieties and some results for those with some degeneration (with an appendix by Walter Gubler: the minimal dimension of a canonical measure)

In this paper, we formulate the geometric Bogomolov conjecture for abelian varieties, and give some partial answers to it. In fact, we insist in a main theorem that under some degeneracy condition, a closed subvariety of an abelian variety does not have a dense subset of small points if it is a non-special subvariety. The key of the proof is the study of the minimal dimension of the components of a canonical measure on the tropicalization of the closed subvariety. Then we can apply the tropical version of equidistribution theory due to Gubler. This article includes an appendix by Walter Gubler. He shows that the minimal dimension of the components of a canonical measure is equal to the dimension of the abelian part of the subvariety. We can apply this result to make a further contribution to the geometric Bogomolov conjecture.     

über Homomorphismen Projektiver Hjelmslev-Ebenen

The main result of this paper is a representation theorem for incidence morphisms of desarguesian Hjelmslev planes which preserve basis quadrangles. We prove that each geometric morphism between desarguesian Hjelmslev planes (R), (S) induces a total order of the coordinate ring R and a partial homomorphism from R to S. Conversely we have for each partial homomorphism and every partial order a uniquely determined geometric morphism. By a total order A of a ring R we mean a subring of R such that the elements of R/A are units in R, with inverses lying in A. If we have such a total order A \( \subseteq \) R, a partial homomorphism from R to another ring S is essentially a homomorphism from A to S.     

A Simple Proof of Suzumura's Extension Theorem for Finite Domains With Applications

In this paper we provide a simple proof of the extension theorem for partial orderings due to Suzumura [1983] when the domain of the partial order is finite. The extension theorem due to Szpilrajn [1930] follows from this theorem. Szpilrajns extension theorem is used to show that an asymmetric binary relation is contained in the asymmetric part of a linear order if and only if it is acyclic. This theorem is then applied to prove three results. Finally we introduce the concept of a threshold choice function, and our third result says that such choice functions are the only ones to satisfy a property called functional acyclicity.     

Nonconvergence in the theory of random orders

There are sentences in the first order theory of partial orders for whom the limit probability of the sentence holding for the random partial order of dimension two does not exist. Furthermore there is no decision procedure that distinguishes those sentences which hold almost surely from those which hold almost never.     

Extending partial isomorphisms on finite structures

We prove the following theorem:Let A be a finite structure in a fixed finite relational language,p ₁,...,p _m partial isomorphisms of A. Then there exists a finite structure B, and automorphismsf _i of B extending thep _i 's. This theorem can be used to prove the small index property for the random structure in this language. A special case of this theorem is, if A and B are hypergraphs. In addition we prove the theorem for the case of triangle free graphs.