The dimension of suborders of the Boolean lattice

We consider the order dimension of suborders of the Boolean latticeB _n . In particular we show that the suborder consisting of the middle two levels ofB _n dimension at most of 6 log₃ n. More generally, we show that the suborder consisting of levelss ands+k ofB _n has dimensionO(k ² logn).The research of the second author was supported by Office of Naval Research Grant N00014-90-J-1206.The research of the third author was supported by Grant 93-011-1486 of the Russian Fundamental Research Foundation.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

Incidence posets of trees in posets of large dimension

In this paper, we investigate substructures of partially ordered sets which must be present whenever the dimension is large. We show that for eachn1, ifT is a tree onn vertices and ifP is any poset having dimension at least 4n ⁶, then eitherP or its dual contains the incidence poset ofT as a suborder.     

Posets with large dimension and relatively few critical pairs

The dimension of a poset (partially ordered set)P=(X, P) is the minimum number of linear extensions ofP whose intersection isP. It is also the minimum number of extensions ofP needed to reverse all critical pairs. Since any critical pair is reversed by some extension, the dimensiont never exceeds the number of critical pairsm. This paper analyzes the relationship betweent andm, when 3tmt+2, in terms of induced subposet containment. Ifmt+1 then the poset must containS _t , the standard example of at-dimensional poset. The analysis form=t+2 leads to dimension products and David Kelly's concept of a split. Whent=3 andm=5, the poset must contain eitherS ₃, or the 6-point poset called a chevron, or the chevron's dual. Whent4 andm=t+2, the poset must containS _t , or the dimension product of the Kelly split of a chevron andS _t–3, or the dual of this product.     

Explicit matchings in the middle levels of the Boolean lattice

New classes of explicit matchings for the bipartite graph (k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that (k) is Hamiltonian.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8041281.     

The dimension of orthomodular posets constructed by pasting Boolean algebras

The main aim of this paper is the calculation of the dimension of certain atomic amalgams. These consist of finite Boolean algebras (blocks) pasted together in such a way that a pair of blocks intersects either trivially in the bounds, or the intersection consists of the bounds, an atom, and its complement.     

The order dimension of multinomial lattices

Using the notion of Ferrers dimension of incidence structures, the order dimension of multi-nomial lattices (i.e. lattices of multi-permutations) is determined. In particular, it is shown that the lattice of all permutations on ann-element set has dimensionn–1.     

On the Boolean dimension of spherical orders

It is well known that if a planar order P is bounded, i.e. has only one minimum and one maximum, then the dimension of P (LD(P)) is at most 2, and if we remove the restriction that P has only one maximum then LD(P)3. However, the dimension of a bounded order drawn on the sphere can be arbitrarily large.The Boolean dimension BD(P) of a poset P is the minimum number of linear orders such that the order relation of P can be written as some Boolean combination of the linear orders. We show that the Boolean dimension of bounded spherical orders is never greater than 4, and is not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs.Part of this work was carried out while both authors were visiting the Department of Applied Mathematics (KAM) of Charles University, Prague. The authors acknowledge support from the EU HCM project DONET.     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

Properties of intersecting families of ordered sets

The first part of this paper deals with families of ordered k-tuples having a common element in different position. A quite general theorem is given and special cases are considered. The second part deals with t families of sets with some intersection properties, and generalizes results by Bollobás, Frankl, Lovász and Füredi to this case.     

Applications of the symmetric chain decomposition of the lattice of divisors

The symmetric chain decomposition of the lattice of divisors,D _N, is applied to prove results about the strict unimodality of the Whitney numbers ofD _N, about minimum interval covers for the union of consecutive rank-sets ofD _N, and about the distribution of sums of vectors in which each vector can be included several times (an extension of the famous Littlewood-Offord problem)Research supported in part by NSA/MSP GrantMDA904-92H3053.     

On the contraction of vectorial lattice representations

For modular lattices of finite length, vector space representations are shown to give rise to contracted representations of homomorphic imagesDedicated to the memory of Alan Day     

Chromatic number of Hasse diagrams,eyebrows and dimension

We construct posets of dimension 2 with highly chromatic Hasse diagrams. This solves a previous problem by Nesetril and Trotter.     

On the connectedness of the complement of the zero-divisor graph of a poset

Abstract

In this paper, connectedness is completely characterized for the complements of the zero-divisor graphs of partially ordered sets. These results are applied to annihilating ideal graphs and intersection graphs of submodules, generalizing some of the work that has recently appeared in the literature.     

Random orders of dimension 2

A relationship is established between (partially) ordered sets of dimension 2 chosen randomly on a labelled set, chosen randomly by isomorphism type, or generated by pairs of random linear orderings. As a consequence we are able to determine the limiting probability (in each of the above sample spaces) that a two-dimensional order is rigid, is uniquely realizable, or has uniquely orientable comparability graph; all these probabilities lie strictly between 0 and 1. Finally, we show that the number of 2-dimensional (partial) orderings of a labelled n-element set is .On leave from Emory University, Atlanta, GA. Research at Emory supported by ONR grant N00014 85-K-0769.     

Interval dimension and MacNeille completion

Equality between the interval dimensions of a poset and its MacNeille completion, announced in [7], has been obtained by the authors as a byproduct of their study of Galois lattices in [8]. The purpose of this note is to give a direct proof, similar to the classical proof of Baker's result stating that the dimension (in the Dushnik-Miller sense) of a poset and its MacNeille completion are the same.Supported by French PRC Math-Info.     

On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

and let be the collection of all subsets of [n] ordered by inclusion. is a cutset if it meets every maximal chain in , and the width of is the minimum number of chains in a chain decomposition of . Fix . What is the smallest value of such that there exists a cutset that consists only of subsets of sizes between m and l, and such that it contains exactly k subsets of size i for each ? The answer, which we denote by , gives a lower estimate for the width of a cutset between levels m and l in . After using the Kruskal–Katona Theorem to give a general characterization of cutsets in terms of the number and sizes of their elements, we find lower and upper bounds (as well as some exact values) for . Received September 4, 1997     

A study of the order dimension of a poset using matrices

In every finite poset (X, ≤) we assign the so called order-matrix , where α_ij ∈ {?2, 0, 1, 2}. Using this matrix, we characterize the order dimension of an arbitrary finite poset.     

Random k-dimensional orders: Width and number of linear extensions

We consider the width W _k (n) and number L _k (n) of linear extensions of a random k-dimensional order P _k (n). We show that, for each fixed k, almost surely W _k (n) lies between (k/2–C)n _1–1/k and 4kn ^1-1/k , for some constant C, and L _k (n) lies between (e ^-2 n ^1-1/k ) ⁿ and (2kn ^1-1/k ) ⁿ . The bounds given also apply to the expectations of the corresponding random variables. We also show that W _k (n) and log L _k (n) are sharply concentrated about their means.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.