Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Traditionally, the trees studied in infinite graphs are trees of height at most ω, with each node adjacent to its parent and its children (and every branch of the tree inducing a path or a ray). However, there is also a method, systematically introduced by Brochet and Diestel, of turning arbitrary well-founded order trees T into graphs, in a way such that every T-branch induces a generalised path in the sense of Rado. This article contains an introduction to this method and then surveys four recent applications of order trees to infinite graphs, with relevance for well-quasi orderings, Hadwiger’s conjecture, normal spanning trees and end-structure, the last two addressing long-standing open problems by Halin. PubDate: 2022-05-02

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We investigate higher-dimensional \(\Delta\) -systems indexed by finite sets of ordinals, isolating a particular definition thereof and proving a higher-dimensional version of the classical \(\Delta\) -system lemma. We focus in particular on systems that consist of sets of ordinals, in which case useful order-theoretic uniformities can be ensured. We then present three applications of these higher-dimensional \(\Delta\) -systems to problems involving the interplay between forcing and partition relations on the reals. PubDate: 2022-04-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract For a (finite) partially ordered set (poset) P, we call a dominating set D in the comparability graph of P, an order-sensitive dominating set in P if either x ∈ D or else a < x < b in P for some a,b ∈ D for every element x in P which is neither maximal nor minimal, and denote by γos(P), the least size of an order-sensitive dominating set of P. For every graph G and integer \(k\geqslant 2\) , we associate to G a graded poset \({\mathscr{P}}_{k}(G)\) of height k, and prove that \(\gamma _{\text {os}}({\mathscr{P}}_{3}(G))=\gamma _{\text {R}}(G)\) and \(\gamma _{\text {os}}({\mathscr{P}}_{4}(G))=2\gamma (G)\) hold, where γ(G) and γR(G) are the domination and Roman domination number of G respectively. Moreover, we show that the order-sensitive domination number of a poset P exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of P. PubDate: 2022-04-27

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In the context of combinatorial reciprocity, it is a natural question to ask what “ \(-Q\) ” is for a poset Q. In a previous work, the definition “ \(-Q:=Q\times \mathbb {R}\) with lexicographic order” was proposed based on the notion of Euler characteristic of semialgebraic sets. In fact, by using this definition, Stanley’s reciprocity for order polynomials was generalized to an equality for the Euler characteristics of certain spaces of increasing maps between posets. The purpose of this paper is to refine this result, that is, to show that these spaces are homeomorphic if the topology of Q is metrizable. PubDate: 2022-04-20

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let n denote a positive integer. We describe the absolute retracts for the following five categories of finite lattices: (1) slim semimodular lattices, which were introduced by G. Grätzer and E. Knapp in (Acta. Sci. Math. (Szeged), 73 445–462 2007), and they have been intensively studied since then, (2) finite distributive lattices (3) at most n-dimensional finite distributive lattices, (4) at most n-dimensional finite distributive lattices with cover-preserving {0,1}-homomorphisms, and (5) finite distributive lattices with cover-preserving {0,1}-homomorphisms. Although the singleton lattice is the only absolute retract for the first category, this result has paved the way to some other classes. For the second category, we prove that the absolute retracts are exactly the finite boolean lattices; this generalizes a 1979 result of J. Schmid. For the third category and also for the fourth, the absolute retracts are the finite boolean lattices of dimension at most n and the direct products of n nontrivial finite chains. For the fifth category, the absolute retracts are the same as those for the second category. Also, we point out that in each of these classes, the algebraically closed lattices and the strongly algebraically closed lattices (investigated by J. Schmid and, in several papers, by A. Molkhasi) are the same as the absolute retracts. PubDate: 2022-04-19

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study the minor relation for algebra homomorphims in finitely generated quasivarieties that admit a logarithmic natural duality. We characterize the minor homomorphism posets of finite algebras in terms of disjoint unions of dual partition lattices and investigate reconstruction problems for homomorphisms. PubDate: 2022-04-08

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We show that the category CPO of chain-complete posets is not co-wellpowered but that it is weakly co-wellpowered. This implies that CPO is nearly locally presentable. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Given a set M, let \({\mathcal O}(M)\) be the set of all the total strict linear orders on M and, given an integer 2 ≤ k ≤ M , let \({\mathcal O}_{k}(M) = \{{\mathbf R} \in {\mathcal O}(N) : \text {\textit {N} is a \textit {k}-subset of \textit {M}}\}\) , that is, let \({\mathcal O}_{k}(M)\) be the family of all the total strict linear orders on each of all the k-subsets of M. A subset \({\mathcal T}\subseteq {\mathcal O}_{k}(M)\) will be called congruent if given any pair \(\{a,b\}\subseteq M\) , if for some \({\mathbf R} \in {\mathcal T}\) we have (a,b) ∈R, then for every \({\mathbf Q}\in {\mathcal T}\) we have (b,a)∉Q. A subset \({\mathcal T}\subseteq {\mathcal O}_{k}(M)\) will be called a k-transversal of \({\mathcal O}(M)\) if for every \({\mathbf R} \in {\mathcal O}(M)\) there is \({\mathbf Q} \in {\mathcal T}\) such that either \({\mathbf Q} \subseteq {\mathbf R}\) or \({\mathbf Q}^{-}\subseteq {\mathbf R}\) (where Q− = {(b,a) : (a,b) ∈Q} is the inverse order of Q). A subset \({\mathcal T}\subseteq {\mathcal O}_{k}(M)\) will be called a congruent k-transversal of \({\mathcal O}(M)\) if \({\mathcal T}\) is congruent and is a k-transversal of \({\mathcal O}(M)\) . In this note we characterize, in terms of 2-arc-colourings of digraphs, the sets of congruent k-transversals of a given set \({\mathcal O}(M)\) . Also we show some relations between these structures with the diagonal Ramsey numbers and with the chromatic number. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Kong and Ribemboim (1994) define for every poset P a sequence P = D0(P), D(P), D2(P), D3(P)… of posets, where Di(P) = D(Di− 1(P)) consists of all maximal antichains of Di− 1(P). They prove that for a finite poset P, there exists an integer i ≥ 0 such that Di(P) is a chain. In this paper, for every finite poset P, we show how to calculate the smallest integer i for which Di(P) is a chain. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper establishes a connection between binary subwords and perfect matchings of a snake graph, an important tool in the theory of cluster algebras. Every binary expansion w can be associated to a piecewise-linear poset P and a snake graph G. We construct a tree structure called the antichain trie which is isomorphic to the trie of subwords introduced by Leroy, Rigo, and Stipulanti. We then present bijections from the subwords of w to the antichains of P and to the perfect matchings of G. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Suppose k ≥ 2 is an integer. Let Yk be the poset with elements x1,x2,y1,y2,…,yk− 1 such that y1 < y2 < ⋯ < yk− 1 < x1,x2 and let \(Y_{k}^{\prime }\) be the same poset but all relations reversed. We say that a family of subsets of [n] contains a copy of Yk on consecutive levels if it contains k + 1 subsets F1,F2,G1,G2,…,Gk− 1 such that G1 ⊂ G2 ⊂⋯ ⊂ Gk− 1 ⊂ F1,F2 and F1 = F2 = Gk− 1 + 1 = Gk− 2 + 2 = ⋯ = G1 + k − 1. If both Yk and \(Y^{\prime }_{k}\) on consecutive levels are forbidden, the size of the largest such family is denoted by \(\text {La}_{\mathrm {c}}\left (n, Y_{k}, Y^{\prime }_{k}\right )\) . In this paper, we will determine the exact value of \(\text {La}_{\mathrm {c}}\left (n, Y_{k}, Y^{\prime }_{k}\right )\) . PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A pseudo ordered set (X,≤) is a set X with a binary relation ≤ that is reflexive and antisymmetric. We associate to a pseudo ordered set X, a partially ordered set Γ(X) called the covering poset. Taking any completion (C,f) of the covering poset Γ(X), and a special equivalence relation ðœƒ on this completion, yields a completion C/ðœƒ of the pseudo ordered set X. The case when (C,f) is the MacNeille completion of Γ(X) gives the pseudo MacNeille completion of X. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We describe a partial order on finite simplicial complexes. This partial order provides a poset stratification of the product of the Ran space of a metric space and the nonnegative real numbers, through the Čech simplicial complex. We show that paths in this product space respecting its stratification induce simplicial maps between the endpoints of the path. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Cover-incomparability graphs (C-I graphs) are graphs whose edge-set is the union of edge-sets of the incomparability graph and the cover graph of some poset. C-I graphs captured attention as an interesting class of graphs from posets. It is known that the recognition of C-I graphs is NP-complete (Maxová et al., Order 26(3), 229–236, 2009). Hence, the problem of finding a particular graph family of C-I graphs whose recognition complexity is polynomial is interesting. We present a new forbidden subgraph characterization of Ptolemaic C-I graphs and a linear time algorithm for its recognition. The characterization of chordal C-I graph is an unsolved problem in this area for quite some time. In this paper, we characterize the family of chordal C-I graphs. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Contrary to the expectation arising from the tanglegram Kuratowski theorem of Czabarka et al. (SIAM J. Discrete Math. 31(3), 1732–1750, 2017), we construct an infinite antichain of planar tanglegrams with respect to the induced subtanglegram partial order. R.E. Tarjan, R. Laver, D.A. Spielman and M. Bóna, and possibly others, showed that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain, i.e., there exists an infinite collection of permutations, such that none of them contains another as a pattern. Our construction adds a twist to the construction of Spielman and Bóna (Electr. J. Comb. 7, N2, 2000). PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The k-th spectral moment Mk(G) of the adjacency matrix of a graph G represents the number of closed walks of length k in G. We study here the partial order ≼ of graphs, defined by G ≼ H if Mk(G) ≤ Mk(H) for all k ≥ 0, and are interested in the question when is ≼ a linear order within a specified set of graphs' Our main result is that ≼ is a linear order on each set of starlike trees with constant number of vertices. Recall that a connected graph G is a starlike tree if it has a vertex u such that the components of G − u are paths, called the branches of G. It turns out that the ≼ ordering of starlike trees with constant number of vertices coincides with the shortlex order of sorted sequence of their branch lengths. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A vertical 2-sum of a two-coatom lattice L and a two-atom lattice U is obtained by removing the top of L and the bottom of U, and identifying the coatoms of L with the atoms of U. This operation creates one or two nonisomorphic lattices depending on the symmetry case. Here the symmetry cases are analyzed, and a recurrence relation is presented that expresses the number of nonisomorphic vertical 2-sums in some desired family of graded lattices. Nonisomorphic, vertically indecomposable modular and distributive lattices are counted and classified up to 35 and 60 elements respectively. Asymptotically their numbers are shown to be at least Ω(2.3122n) and Ω(1.7250n), where n is the number of elements. The number of semimodular lattices is shown to grow faster than any exponential in n. PubDate: 2022-04-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A topology is said to be strongly useful if every weakly continuous preorder admits a continuous order-preserving function. A strongly useful topology is useful, in the sense that every continuous total preorder admits a continuous utility representation. In this paper, I study the structure of strongly useful topologies. The existence of a natural one-to-one correspondence is proved, between weakly continuous preorders and equivalence classes of families of complete separable systems. In some sense, this result completely clarifies the connections between order theory and topology. Then, I characterize strongly useful topologies and I present a property concerning subspace topologies of strongly useful topological spaces. PubDate: 2022-03-23

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: As an abstraction and generalization of the integral operator in analysis, integral operators (known as Rota-Baxter operators of weight zero) on associative algebras and Lie algebras have played an important role in mathematics and physics. This paper initiates the study of integral operators on lattices and the resulting Rota-Baxter lattices (of weight zero). We show that properties of lattices can be characterized in terms of their integral operators. We also display a large number of integral operators on any given lattice and classify the isomorphism classes of integral operators on some common classes of lattices. We further investigate structures on semirings derived from differential and integral operators on lattices. PubDate: 2022-03-05 DOI: 10.1007/s11083-021-09593-0

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We investigate connections between the free lattice generated by a poset while preserving certain bounds and the canonical extension of a poset. Explicitly, we describe how the free lattice generated by a poset while preserving certain bounds can be constructed as a colimit of ‘intermediate structures’as they occur in the construction of a canonical extension of a poset. PubDate: 2022-02-22 DOI: 10.1007/s11083-022-09594-7