Strictly Order-Preserving Maps into Z, II. A 1979 Problem of Erné

A lattice L is constructed with the property that every interval has finite height, but there exists no strictly order-preserving map from L to Z. A 1979 problem of Erné (posed at the 1981 Banff Conference on Ordered Sets) is thus solved. It is also shown that if a poset P has no uncountable antichains, then it admits a strictly order-preserving map into Z if and only if every interval has finite height.     

Interval orders and circle orders

A finite poset is an interval order if its point can be mapped into real intervals so that x in the poset precisely when x's interval lies wholly to the left of y's; the poset is a circle order if its points can be mapped into circular disks in the plane so that x precisely when x's circular disk is properly included in y's. This note proves that every finite interval order is a circle order.     

When Will Every Maximal <Emphasis Type="BoldItalic">F</Emphasis>-free Subposet Contain a Maximal Element?

Let F be a partially ordered set (poset). A poset P is called F-free if P contains no subposet isomorphic to F. A finite poset F is said to have the maximal element property if every maximal F-free subposet of any finite poset P contains a maximal element of P. It is shown that a poset F with at least two elements has the maximal element property if and only if F is an antichain or F ≅ 2 + 2.     

Circle orders and angle orders

A poset is a circle order if its points can be mapped into circular disks in the plane so that x in the poset precisely when x's circular disk is properly included in y's; the poset is an angle order if its points can be mapped into unbounded angular regions that preserve < by proper inclusion. It is well known that many finite angle orders are not circle orders, but has been open as to whether every finite circle order is an angle order. This paper proves that there are finite circle orders that are not angle orders.     

Posets with the Maximal Antichain Property

A finite poset F has the maximal antichain property if every maximal F-free subposet of every finite poset P contains a maximal antichain of P. We find all finite posets with the maximal antichain property.     

The lattice of strict completions of a finite poset

For a given finite poset , we construct strict completions of P which are models of all finite lattices L such that the set of join-irreducible elements of L is isomorphic to P. This family of lattices, , turns out to be itself a lattice, which is lower bounded and lower semimodular. We determine the join-irreducible elements of this lattice. We relate properties of the lattice to properties of our given poset P, and in particular we characterize the posets P for which . Finally we study the case where is distributive. Received October 13, 2000; accepted in final form June 13, 2001.     

Going down in (semi)lattices of finite moore families and convex geometries

In this paper we first study what changes occur in the posets of irreducible elements when one goes from an arbitrary Moore family (respectively, a convex geometry) to one of its lower covers in the lattice of all Moore families (respectively, in the semilattice of all convex geometries) defined on a finite set. Then we study the set of all convex geometries which have the same poset of join-irreducible elements. We show that this set—ordered by set inclusion—is a ranked join-semilattice and we characterize its cover relation. We prove that the lattice of all ideals of a given poset P is the only convex geometry having a poset of join-irreducible elements isomorphic to P if and only if the width of P is less than 3. Finally, we give an algorithm for computing all convex geometries having the same poset of join-irreducible elements.      

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.     

The poset structures admitting the extended binary Golay code to be a perfect code

Brualdi et al. [Codes with a poset metric, Discrete Math. 147 (1995) 57-72] introduced the concept of poset codes, and gave an example of poset structure which admits the extended binary Golay code to be a 4-error-correcting perfect P-code. In this paper we classify all of the poset structures which admit the extended binary Golay code to be a 4-error-correcting perfect P-code, and show that there are no posets which admit the extended binary Golay code to be a 5-error-correcting perfect P-code.     

Chain partitions of ordered sets

For natural numbers s and r and a finite poset P of height h, there exists a finite poset P of height H(s, r, h) such that for an arbitrary r-colouring of the s-chains of P, a monochromatically embedded copy of P can be found in P. A best possible upper bound for H(s, r, h) in terms of the well-known Ramsey numbers is given.     

Paths extendable to cycles

Let k be a positive integer, and S a nonempty set of positive integers. Suppose that G is a connected graph containing a path of length k, and that each path P of length k in G is contained in some cycle C(P) of length s ∈ S. We prove that every path of length less than k can be extended to a path of length k in G. This result answers conjectures of Entringer and Reid regarding when certain paths may be extended to cycles.     

Groups isomorphic to all their non-trivial normal subgroups

A finite collectionP of finite sets tiles the integers iff the integers can be expressed as a disjoint union of translates of members ofP. We associate with such a tiling a doubly infinite sequence with entries fromP. The set of all such sequences is a sofic system, called a tiling system. We show that, up to powers of the shift, every shift of finite type can be realized as a tiling system. Some of this work was done at the Mathematical Sciences Research Institute (MSRI), where research is supported in part by NSF grant DMS-9701755. The first two authors thank K. Schmidt for useful conversations and ideas.     

Mailbox¶A Note on minimal varieties generated by order-primal algebras

We prove that the order-primal algebra of a non-trivial finite connected poset P generates a minimal variety if and only if P is dismantlable. Received November 26, 2002; accepted in final form January 24, 2003.     

On the representation of partially ordered sets

It is well known that any distributive poset (short for partially ordered set) has an isomorphic representation as a poset (Q, ⊆) such that the supremum and the infimum of any finite setF ofP correspond, respectively to the union and intersection of the images of the elements ofF. Here necessary and sufficient conditions are given for similar isomophic representation of a poset where however the supremum and infimum of also infinite subsetsI correspond to the union and intersection of images of elements ofI.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

How To Split Antichains In Infinite Posets*

A maximal antichain A of poset P splits if and only if there is a set B ⊂ A such that for each p ∈ P either b ≤ p for some b ∈ B or p ≤ c for some c ∈ A\B. The poset P is cut-free if and only if there are no x < y < z in P such that [x,z]_P = [x,y]_P ∪ [y,z]_P . By [1] every maximal antichain in a finite cut-free poset splits. Although this statement for infinite posets fails (see [2])) we prove here that if a maximal antichain in a cut-free poset “resembles” to a finite set then it splits. We also show that a version of this theorem is just equivalent to Axiom of Choice. We also investigate possible strengthening of the statements that “A does not split” and we could find a maximal strengthening. * This work was supported, in part, by Hungarian NSF, under contract Nos. T37846, T34702, T37758, AT 048 826, NK 62321. The second author was also supported by Bolyai Grant.     

On the Möbius function of the locally finite poset associated with a numerical semigroup

Let S be a numerical semigroup and let (?,≤ _S ) be the (locally finite) poset induced by S on the set of integers ? defined by x≤ _S y if and only if y?x∈S for all integers x and y. In this paper, we investigate the Möbius function associated to (?,≤ _S ) when S is an arithmetic semigroup.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

A test for conjugacy of partitions of finite sets

In this note we present a simple test, involving a sequence of integers, which assures the conjugacy of a given partition P of a finite set S when our operations lead only to nonnegative integers. If negative integers appear in our operations, our test is inconclusive. The test, when conclusive, and an elementary property of permutations determine a conjugate for P.