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.
We study a min-max relation conjectured by Saks and West: For any two posets P and Q the size of a maximum semiantichain and the size of a minimum unichain covering in the product P×Q are equal. As a positive result, we state conditions on P and Q that imply the min-max relation. Based on these conditions we identify some new families of posets where the conjecture holds and get easy proofs for several...
We shed some new light to the problem of characterizing those functions of several arguments that have a unique identification minor. The 2-set-transitive functions are known to have this property. We describe another class of functions that have a unique identification minor, namely functions determined by the order of first occurrence. We also present some examples of other kinds of functions with...
Dorais asked for the maximum guaranteed size of a subposet with dimension at most d of an n-element poset. A lower bound of order n was found by Goodwillie. We provide a sublinear upper bound for each d. For d = 2, our bound is n0.8295.
We investigate the class of intersection graphs of paths on a grid (VPG graphs), and specifically the relationship between the bending number of a cocomparability graph and the poset dimension of its complement. We show that the bending number of a cocomparability graph G is at most the poset dimension of the complement of G minus one. Then, via Ramsey type arguments, we show our upper bound is best...
A recent result of Aharoni Berger and Gorelik (Order 31(1), 35–43, 2014) is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow (Theory Ser. B 33(3), 271–275, 1982) on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to...
We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the...
A careful study is made of embeddings of posets which have a convex range. We observe that such embeddings share nice properties with the homomorphisms of more restrictive categories; for example, we show that every order embedding between two lattices with convex range is a continuous lattice homomorphism. A number of posets are considered; for one of the simplest examples, we prove that every product...
A poset P = (X, ≺) is a unit OC interval order if there exists a representation that assigns an open or closed real interval I(x) of unit length to each x ∈ P so that x ≺ y in P precisely when each point of I (x) is less than each point in I (y). In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The...
In this short note we would like to point out a straighforward corllary of the recent result of Dorais, Gubkin, McDonald and Rivera that the automorphism group of every ω-categorical linear order is extremely amenable: it follows that an oligomorphic permutation group G is contained in an extremely amenable permutation group if and only if it preserves a linear order.
We characterize conservative median algebras and semilattices by means of forbidden substructures and by providing their representation as chains. Moreover, using a dual equivalence between median algebras and certain topological structures, we obtain descriptions of the median-preserving mappings between products of finitely many chains.
Kahn and Kim (J. Comput. Sci. 51, 3, 390–399, 1995) have shown that for a finite poset P, the entropy of the incomparability graph of P (normalized by multiplying by the order of P) and the base-2 logarithm of the number of linear extensions of P are within constant factors from each other. The tight constant for the upper bound was recently shown to be 2 by Cardinal et al. (Combinatorica 33, 655–697,...
This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected...
Let L be a lattice of finite length, ξ = (x1,…, xk)∈Lk, and y ∈ L. The remotenessr(y, ξ) of y from ξ is d(y, x1)+⋯+d(y, xk), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice...
In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset...
We give new interpretations of Catalan and convoluted Catalan numbers in terms of trees and chain blockers. For a poset P we say that a subset A ⊆ P is a chain blocker if it is an inclusionwise minimal subset of P that contains at least one element from every maximal chain. In particular, we study the set of chain blockers for the class of posets P = Ca × C ...
We characterize ultrafilter convergence and ultrafilter compactness in linearly ordered and generalized ordered topological spaces. In such spaces, and for every ultrafilter D, the notions of D-compactness and of D-pseudocompactness are equivalent. Any product of initially λ-compact generalized ordered topological spaces is still initially λ-compact. On the other hand, preservation under products...
Papert Strauss (Proc. London Math. Soc. 18(3), 217–230, 1968) used Pontryagin duality to prove that a compact Hausdorff topological Boolean algebra is a powerset algebra. We give a more elementary proof of this result that relies on a version of Bogolyubov’s lemma.
Let CONT≪ be the category of continuous domains and Scott continuous mappings that preserve the way-below relation on domains. Let ω-ALG≪ be the full subcategory of CONT≪ consisting of all countably based algebraic domains, and F I N be the category of finite posets and monotone mappings. The main result proved in this paper is that F I N is the largest Cartesian closed...
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.