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.     

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 dimension of interior levels of the Boolean lattice

LetP(k,r;n) denote the containment order generated by thek-element andr-element subsets of ann-element set, and letd(k,r;n) be its dimension. Previous research in this area has focused on the casek=1.P(1,n–1;n) is the standard example of ann-dimensional poset, and Dushnik determined the value ofd(1,r;n) exactly, whenr2 . Spencer used the Erdös-Szekeres theorem to show thatd(1, 2;n) lg lgn, and he used the concept of scrambling families of sets to show thatd(1,r;n)=(lg lgn) for fixedr. Füredi, Hajnal, Rödl and Trotter proved thatd(1, 2;n)=lg lgn+(1/2+o(1))lg lg lgn. In this paper, we concentrate on the casek2. We show thatP(2,n–2;n) is (n–1)-irreducible, and we investigated(2,r;n) whenr2 , obtaining the exact value for almost allr.The research was supported in part by NSF grant DMS 9201467.The research was supported in part by the Universities in Russia program.     

Maximizing antichains in the cube with fixed size of a shadow

In the n-dimensional cube, we determine the maximum size of antichains having a lower shadow of exactly m elements in the k-th level.     

Some generalizations of Property B and the splitting property

The set system satisfiesProperty B if there exists a partitionX ₁X ₂=X such that any element of intersects both classes. Here, we study the following problem: We are givenk set systems on the underlying setX, and we are seeking ak-partition ofX such that any element of theith set system intersectsX _i for everyi.The paper received its final form when the author enjoyed the hospitality of L.A. Székely of the University of South Carolina, Columbia, South Carolina, USA. The research was partially supported by the Hungarian Scientific Fund, Grant no. T16358.     

A splitting property of maximal antichains

In anydense posetP (and in any Boolean lattice in particular) every maximal antichainS may be partitioned into disjoint subsetsS ₁ andS ₂, such that the union of the downset ofS ₁ with the upset ofS ₂ yields the entire poset:D(S ₁) U (S ₂) =P. To find a similar splitting of maximal antichains in posets is NP-hard in general.Research was partially carried out when the second author visited the first author in Bielefeld and it was partially supported by OTKA grant T016358     

Chain partitions of ordered sets

For natural numbers s and r and a finite poset P of height h, there exists a finite poset P of height H(s, r, h) such that for an arbitrary r-colouring of the s-chains of P, a monochromatically embedded copy of P can be found in P. A best possible upper bound for H(s, r, h) in terms of the well-known Ramsey numbers is given.     

Primal decomposition in rings, modules and lattice modules

In a work by L. Fuchs, W. Heinzer and B. Olberding, a decomposition of ideals in a commutative ring as intersections of primal isolated component ideals is investigated. In subsequent work by L. Fuchs and R. Reis, these ideas are developed in multiplicative lattices. The object of this note is to point out that, when specialized to the lattice of ideals of a commutative ring, the decomposition of L. Fuchs and R. Reis does not give the decomposition obtained in the paper by Fuchs, Heinzer and Olberding, and to give two variations of the decomposition of Fuchs and Reis. One of these variations, when specialized to the lattice of ideals of a ring, does give the decomposition obtained by Fuchs, Heinzer and Olberding, and the other one gives a decomposition which is superior in some ways. Received December 2, 2004; accepted in final form February 17, 2005.     

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.     

A Simplicial elimination scheme for ⋀-semidistributive lattices and interval collapsing

The purpose of this paper is first to show that -semidistributive lattices can be characterized by a simplicial elimination scheme in the same sense as upper locally distributive lattices or antimatroids. Secondly, we show that this elimination scheme leads to an interval collapsing algorithm and a constructing algorithm for semidistributive lattices.     

Proof of a conjecture on the Sperner property of the subgroup lattice of an abelianp-group

Let (p) denote the subgroup lattice of the abelianp-group

On weak lattice and frame homomorphisms

In the context of distributive lattices, frames, or -frames, a join homomorphism preserving the unit and those binary meets which are zero often preserves all binary meets. This paper analyzes this phenomenon.     

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.     

The Frattini sublattice of a finite distributive lattice

Frattini sublattices of finite distributive lattices are characterized and several applications are given thereof.Presented by J. Berman.The support of Consejo Nacional de Investigaciones Cientificas y Técnicas de la República Argentina is gratefully acknowledged.     

Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders

We consider the poset SO(n) of all words over an n-element alphabet ordered by the subword relation. It is known that SO(2) falls into the class of Macaulay posets, i. e. there is a theorem of Kruskal–Katona type for SO(2). As the corresponding linear ordering of the elements of SO(2) the vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n3 by explicitly giving a counterexample. Based on this, we prove that for no n3 the subword order SO(n) is a Macaulay poset.     

Largest induced suborders satisfying the chain condition

For a finite ordered set P, let c(P) denote the cardinality of the largest subset Q such that the induced suborder on Q satisfies the Jordan-Dedekind chain condition (JDCC), i.e., every maximal chain in Q has the same cardinality. For positive integers n, let f(n) be the minimum of c(P) over all ordered sets P of cardinality n. We prove:      

Minimum cutsets for an element of a boolean lattice

An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B _n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B _n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076.     

A partial order for the set of meanders

In this paper, we present a new approach for studying meanders in terms of noncrossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.