On the size of maximal antichains and the number of pairwise disjoint maximal chains

Fix integers n and k with n≥k≥3. Duffus and Sands proved that if P is a finite poset and n≤|C|≤n+(n−k)/(k−2) for every maximal chain in P, then P must contain k pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if P is a finite poset and n≤|A|≤n+(n−k)/(k−2) for every maximal antichain in P, then P has k pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.     

Order-couniversality of the complete infinitary tree: An application of zero-divisor graphs

Let

be the class of countably infinite bounded partially ordered sets

such that every non-minimum element of

has only finitely many successors, and has infinitely many immediate predecessors. Write

for the poset obtained by introducing maximum and minimum elements to the complete infinitary tree of nonempty finite sequences

of positive integers, where

if

is an extension of

. A poset

is called

-couniversal if

and for every

there is a bijective poset-homomorphism

. In this paper, couniversality is linked to zero-divisor graphs of partially ordered sets. It is proved that

is

-couniversal if and only if every non-maximum element of

is a (poset-theoretic) zero-divisor of

, and the zero-divisor graph of

is a spanning subgraph of the zero-divisor graph of

.     

关于偏序集相关联图的色数

对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1.     

On Pseudocomplemented and Stone Ordered Sets

The aim of this paper is to characterize both the pseudocomplemented and Stone ordered sets in a manner similar to that used previously for Boolean and distributive ordered sets. The sublattice G(A) of the Dedekind–Mac Neille completion DM(A) of an ordered set A generated by A is said to be the characteristic lattice of A. We will show that there are distributive pseudocomplemented ordered sets whose characteristic lattices are not pseudocomplemented. We can define a stronger notion of pseudocomplementedness by demanding that both A and G(A) be pseudocomplemented. It turns out that the two concepts are the same for finite and Stone ordered sets.     

偏序集的关联环的同构问题

设Ｘ是局部有限偏序集（或拟序集），Ｒ是含１的结合环，Ⅰ（Ｘ，Ｒ）是Ｒ上Ｘ的关联环，关联环的同构问题是指：问题１：怎样的环，能使环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｒ）推出偏序集之间的同构Ｘ芒Ｘ’？问题２：怎样的环或偏序集，能使环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｓ）推出Ｒ　Ｓ？本文证明了对唯一幂等元环（非交换），问题１有正面回答；对问题２，我们证明了对交换不可分解环Ｒ、Ｓ，由环同构Ⅰ（Ｘ，Ｒ）Ⅰ（Ｘ，Ｒ）可得到Ｒ＝Ｓ，Ｘ＝Ｘ’。     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Can transitive orientation make sandwich problems easier?

A graph G_s=(V,E_s) is a sandwich for a pair of graphs G_t=(V,E_t) and G=(V,E) if E_t⊆E_s⊆E. A sandwich problem asks for the existence of a sandwich graph having an expected property. In a seminal paper, Golumbic et al. [Graph sandwich problems, J. Algorithms 19 (1995) 449-473] present many results on sub-families of perfect graphs. We are especially interested in comparability (resp., co-comparability) graphs because these graphs (resp., their complements) admit one or more transitive orientations (each orientation is a partially ordered set or poset). Thus, fixing the orientations of the edges of G_t and G restricts the number of possible sandwiches. We study whether adding an orientation can decrease the complexity of the problem. Two different types of problems should be considered depending on the transitivity of the orientation: the poset sandwich problems and the directed sandwich problems. The orientations added to both graphs G and G_s are transitive in the first type of problem but arbitrary for the second type.     

Combinatorial Criteria for Ramifiable Ordered Sets

The tree‐property (classica in cardina theory) and its variants make sense also for directed sets and even for partially ordered sets. A combinatoria approach is developed here, with characterizations and criteria involving (inter alia) adequate families of special substructures of directed sets. These substructures form a natural hierarchy that is also investigated.     

Possibilities for the number of invariant polynomials of the difference of two similarity classes

In this paper we describe all possible numbers of (nontrivial) invariant polynomials of the difference of two matrices with prescribed similarity classes over an algebraically closed field.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

Hierarchies of Partially Ordered Connectives and Quantifiers

Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form what is a strengthening of the Walkoe result. MSC: 03C80.     

On similarity relations in fuzzy relational databases

A characterization of a certain type of similarity relation is presented. This characterization is conceptually very easy and may be used to provide easier proofs of already established theorems.We use this characterization to show that if only a few similarity values of a similarity relation are known, then the others may be computed. This results in efficient storage of similarity relations associated with fuzzy relational databases.In addition, we use our characterization to show that there is only one type of similarity relation that provides a non-redundant decomposition of data in a fuzzy relational data base.     

Distributive lattices of small width, II: A problem from Stanley's 1986 text Enumerative Combinatorics

In Richard P. Stanley's 1986 text, Enumerative Combinatorics, the following problem is posed: Fix a natural number k. Consider the posets P of cardinality n such that, for 0<i<n, P has exactly k order ideals (down-sets) of cardinality i. Let fk(n) be the number of such posets. What is the generating function ∑f₃(n)xn?In this paper, the problem is solved.     

Directed complete poset congruences

The study of algebraic properties of ordered structures has shown that their behavior in many cases is different from algebraic structures. For example, the analogues of the fundamental mapping theorem for sets which characterizes surjective maps as quotient sets modulo their kernel relations, is not true for order-preserving maps between posets (partially ordered sets). The main objective of this paper is to study the quotients of dcpos (directed complete partially ordered sets), and their relations with surjective dcpo maps (directed join preserving maps). The motivation of studying such infinitary ordered structures is their importance in domain theory, a theory on the borderline of mathematics and theoretical computer science.In this paper, introducing the notion of a pre-congruence on dcpos (directed complete partially ordered sets), we give a characterization of dcpo congruences. Also, it is proved that unlike natural dcpo congruences, the dcpo congruences are precisely kernels of surjective dcpo maps. Also, while it is known that the image of a dcpo map is not necessarily a subdcpo of its codomain, we find equivalent conditions on a dcpo map to satisfy this property. Moreover, we prove the Decomposition Theorem and its consequences for dcpo maps.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

Searching monotone multi-dimensional arrays

A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A_n,d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether x∈A_n,d, by performing a sequence of comparisons between x and some entries of A_n,d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d?4. For d=4, our new algorithm is optimal up to the lower order terms.     

Cohomology of partially ordered sets and local cohomology of section rings

We study local cohomology of rings of global sections of sheafs on the Alexandrov space of a partially ordered set. We give a criterion for a splitting of the local cohomology groups into summands determined by the cohomology of the poset and the local cohomology of the stalks. The face ring of a rational pointed fan can be considered as the ring of global sections of a flasque sheaf on the face poset of the fan. Thus we obtain a decomposition of the local cohomology of such face rings. Since the Stanley-Reisner ring of a simplicial complex is the face ring of a rational pointed fan, our main result can be interpreted as a generalization of Hochster's decomposition of local cohomology of Stanley-Reisner rings.     

On the Jump Number of Lexicographic Sums of Ordered Sets

Let Q be the lexicographic sum of finite ordered sets Q _x over a finite ordered set P. For some P we can give a formula for the jump number of Q in terms of the jump numbers of Q _x and P, that is, , where s(X) denotes the jump number of an ordered set X. We first show that where w(X) denotes the width of an ordered set X. Consequently, if P is a Dilworth ordered set, that is, s(P) = w(P)–1, then the formula holds. We also show that it holds again if P is bipartite. Finally, we prove that the lexicographic sum of certain jump-critical ordered sets is also jump-critical.