The Automorphism Conjecture for Ordered Sets of Dimension 2 and Interval Orders
- PDF / 270,857 Bytes
- 11 Pages / 439.642 x 666.49 pts Page_size
- 16 Downloads / 165 Views
The Automorphism Conjecture for Ordered Sets of Dimension 2 and Interval Orders 1 ¨ Bernd S. W. Schroder
Received: 28 April 2019 / Accepted: 16 September 2020 / © Springer Nature B.V. 2020
Abstract Let λ ∈ 0, 12 . We prove that, for ordered sets P of order dimension 2 and for interval orders, the ratio of the number of automorphisms to the number of endomorphisms is λ asymptotically bounded by 2−|P | . The key to the proof is to establish this bound for certain types of lexicographic sums. Keywords Ordered set · Automorphism · Order-preserving map · Order dimension 2 · Interval order · Lexicographic sum
1 Introduction An ordered set P consists of an underlying set P equipped with a reflexive, antisymmetric and transitive relation ≤, the order relation. Throughout this paper, order-preserving selfmaps of ordered sets (maps f : P → P such that p ≤ q implies f (p) ≤ f (q)) will also be referred to as endomorphisms. Consistent with standard terminology, endomorphisms with an inverse that is an endomorphism, too, are called automorphisms. Rival and Rutkowski’s automorphism problem (see [11], Problem 3) asks the following. Open Question 1.1 (Automorphism Problem.) Is it true that lim max
n→∞ |P |=n
|Aut(P )| = 0? |End(P )|
The automorphism conjecture states that the the answer to the automorphism problem should be affirmative. A natural way to bound a quotient is, of course, to find lower bounds for the denominator and upper bounds for the numerator.
Bernd S. W. Schr¨oder
[email protected] 1
School of Mathematics and Natural Sciences, The University of Southern Mississippi, 118 College Avenue, #5043, Hattiesburg, MS, 39406, USA
Order 2
Theorem 1.2 (See [2], Theorem 1.) Every ordered set with n elements has at least 2 3 n endomorphisms. In light of Theorem 1.2 and the fact that, for almost every ordered set, the identity is the only automorphism (see [10], Corollary 2.3a), the automorphism conjecture is quite natural. Indeed, it was suggested by Trotter (see [2]) that convergence should be exponential. If, for ordered sets with “many” automorphisms, we could show that there are “enough” endomorphisms to guarantee the ratio’s convergence to zero (see [7, 8] for examples of this technique), the conjecture would be confirmed. However, the automorphism conjecture has been remarkably resilient against attempts to prove it in general. In fact, there does not even seem to be a proof that, for ordered sets with more than one point, the ratio is bounded by 12 ! Two-dimensional ordered sets and interval ordered sets are well established in the theory of ordered sets. Definition 1.3 An ordered set P has dimension 2 iff the order on P is the intersection of two distinct linear orders. Regarding the automorphisms of two-dimensional ordered sets, we can record the following, with indecomposable ordered sets defined in Section 2. Theorem 1.4 (See Lemma 4.2 in [1], Theorem 6 in [6].) Let P be a finite indecomposable two-dimensional ordered set. Then P has at most two automorphisms. For the class of interval ordere
Data Loading...
