The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A monotone grid class is a permutation class (i.e., a downset of permutations under the containment order) defined by local monotonicity conditions. We give a simplified proof of a result of Murphy and Vatter that monotone grid classes of forests are partially well-ordered.
Our first paper introduced block splitting operators on the complete lattice of partial partitions, studied their algebraic properties and characterized block splitting openings (kernel operators) in terms of partial connections. In this second paper we study non-isotone idempotent block splitting operators on partial partitions. In particular we analyse the following two constructions: the residual combination...
Partially ordered sets labeled with k labels (k-posets) and their homomorphisms are examined. We give a representation of directed graphs by k-posets; this provides a new proof of the universality of the homomorphism order of k-posets. This universal order is a distributive lattice. We investigate some other properties, namely the infinite distributivity, the computation of infinite suprema and infima,...
Acyclic monounary algebras are characterized by the property that any compatible partial order r can be extended to a compatible linear order. In the case of rooted monounary algebras ${\cal A}=(A,f)$ we characterize the intersection of compatible linear extensions of r by several equivalent conditions and generalize these results to compatible quasiorders of . We show that the lattice...
We study the connection between the number of ascending and descending cuts of a linear order, its classical size, and its effective complexity (how much [how little] information can be encoded into it).
We prove that if a finite (3 + 1)-free ordered set of height two has the fixed point property, then it is dismantlable by irreducibles. We provide an example of a finite (3 + 1)-free ordered set of height three with the fixed point property and no irreducible elements. We characterize the minimal automorphic ordered sets which are respectively (3 + 1)-free, (2 + 2)-free and N-free.
We find a syntactic characterization of the class $\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}$ of finite lattices embeddable into convexity lattices of a certain class of posets which we call star-like posets and which is a proper subclass in the class of N-free posets. The characterization implies that the class $\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}$ forms a pseudovariety.
Two orders on the same set are orthogonal if the constant maps and the identity map are the only maps preserving both orders. We construct linear orders orthogonal to the order on the rationals.
Sachs (Can J Math 14:451–460, 1962) showed that a Boolean algebra is determined by its lattice of subalgebras. We establish the corresponding result for orthomodular lattices. We show that an orthomodular lattice L is determined by its lattice of subalgebras Sub(L), as well as by its poset of Boolean subalgebras BSub(L). The domain BSub(L) has recently found use in an approach to the foundations of...
Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset PM of a planar map M is at most four. In this paper we investigate cases where dim(PM) ≤ 3 and also where dim(QM) ≤ 3; here QM denotes the vertex-face poset of M. We show: If M contains a K4-subdivision, then dim(PM) = dim(QM) = 4. ...
This paper concerns the classification of finite coloured linear orders up to n-equivalence. Ehrenfeucht–Fraïssé games are used to define what this means, and also to help analyze such structures. We give an explicit bound for the least number g(m,n) such that any finite m-coloured linear order is n-equivalent to some ordering of size ≤ g(m,n), from which it follows that g is computable. We give exact...
We study unit interval graphs and bipartite permutation graphs partially ordered by the induced subgraph relation. It is known that neither of these classes is well-quasi-ordered, since each of them contains an infinite antichain. We show that in both cases the antichains are canonical in the sense that any subclass of unit interval or bipartite permutation graphs containing only finitely many graphs...
This paper gives a characterization of standard elements involving the exclusion of 19 types of sublattices containing it along with a property called the lower separation property for the element. In particular, a characterization of standard elements in M-symmetric lattices by the exclusion of 11 types of sublattices containing it is obtained.
We introduce Priestley rings of upsets (of a poset) and prove that inequivalent Priestley ring representations of a bounded distributive lattice L are in 1-1 correspondence with dense subspaces of the Priestley space of L. This generalizes a 1955 result of Bauer that inequivalent reduced field representations of a Boolean algebra B are in 1-1 correspondence with dense subspaces of the Stone space...
Double basic algebras are a counterpart of bounded lattices with order-antiautomorphisms on principal filters. In the paper, an independent axiomatization of double basic algebras is given and lattice pseudo-effect algebras are characterized in the setting of double basic algebras.
This paper investigates links between some classes of graphs and some classes of lattices. We show that a co-atomic lattice is crown-free (i.e. dismantlable) if and only if it is a maximal clique lattice of a strongly chordal graph. We also prove that each crown-free lattice that is not a chain contains at least two incomparable doubly-irreducible elements x1 and x2 such that ↑ x1 and ↑ x2 are...
Order-compactifications of totally ordered spaces were described by Blatter (J Approx Theory 13:56–65, 1975) and by Kent and Richmond (J Math Math Sci 11(4):683–694, 1988). Their results generalize a similar characterization of order-compactifications of linearly ordered spaces, obtained independently by Fedorčuk (Soviet Math Dokl 7:1011–1014, 1966; Sib Math J 10:124–132, 1969) and Kaufman (Colloq...
A poset is $(\underline{r}+\underline{s})$ -free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every $(\underline{r}+\underline{s})$ -free poset P into at most 8(r − 1)(s − 1)w chains, where w is the width of P. This solves an open problem of Bosek et al. (SIAM J Discrete Math 23(4):1992–1999,...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.