An extension of Boolean lattice theory

Mathematische Annalen -     

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 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.     

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.     

Adjacency in subposets of the lattice of T 1-topologies on a set

Summary We study subposets of the lattice L_₁(X) of all T1-topologies on a set X, namely Σ_t(X), Σ₃(X) and Σ_lc(X), being respectively the collections of all Tychonoff, all T₃ and all locally compact Hausdorff topologies on X, with a view to deciding which elements of these partially ordered sets have and which do not have covers, that is to say immediate successors, in the respective posets. In the final section we discuss the subposet Σ _G of all Hausdorff group topologies on a group G.     

Subdirect decompositions and the radical of a generalized Boolean algebra extension of a lattice ordered group

The extension of a lattice ordered group A by a generalized Boolean algebra B will be denoted by A _B . In this paper we apply subdirect decompositions of A _B for dealing with a question proposed by Conrad and Darnel. Further, in the case when A is linearly ordered we investigate (i) the completely subdirect decompositions of A _B and those of B, and (ii) the values of elements of A _B and the radical R(A _B ).     

Linear operators that preserve Boolean rank of Boolean matrices

The Boolean rank of a nonzero m × n Boolean matrix A is the minimum number k such that there exist an m× k Boolean matrix B and a k × n Boolean matrix C such that A = BC. In the previous research L. B. Beasley and N. J. Pullman obtained that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and 2. In this paper we extend this characterizations of linear operators that preserve the Boolean ranks of Boolean matrices. That is, we obtain that a linear operator preserves Boolean rank if and only if it preserves Boolean ranks 1 and k for some 1 < k ? m.     

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.     

Partitions of a finite Boolean lattice into intervals

Related to activities in matroids, J.E. Dawson introduced a construction that leads to partitions of the Boolean lattice of parts of a set into intervals. In this paper we characterize explicitly the partitions of a Boolean lattice into intervals that arise from this construction, and we prove that the construction is essentially unique.     

Maximal number of Boolean functions realized by an initial Boolean automaton with two constant states

The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of set of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with two constant states and n inputs is obtained.     

Proof of a conjecture on partitions of a Boolean lattice

Let n and c be positive integers. We show that if n is sufficiently large given c then the Boolean lattice consisting of all subsets of an n-element set can be partitioned into chains of size c except for at most c — 1 elements which also form a chain. This settles a conjecture of Griggs.     

Boolean algebras of lattice uniformities and decompositions of modular functions

We study decomposition theorems for modular functions on lattices and the relationship between such decompositions and lattice properties of a suitable system of uniformities. We give a purely topological characterization for the validity of a decomposition theorem of a certain type and examine when this topological condition is satisfied, namely when a system of lattice uniformities is a Boolean algebra consisting of permutable uniformities.      

The determinants of certain matrices arising from the Boolean lattice

Let B be the Boolean lattice on an n-set with B=?B_i the rank decomposition. Let M(n,i) be the incidence matrix between B_i and B_n−i. We obtain a recursive formula for the determinant of the matrix M(n,i).     

Improved bounds on the diameter of lattice polytopes

We show that the largest possible diameter \({\delta(d,k)}\) of a d-dimensional polytope whose vertices have integer coordinates ranging between 0 and k is at most \({kd - \lceil2d/3\rceil-(k-3)}\) when \({k\geq3}\) . In addition, we show that \({\delta(4,3)=8}\) . This substantiates the conjecture whereby \({\delta(d,k)}\) is at most \({\lfloor(k+1)d/2\rfloor}\) and is achieved by a Minkowski sum of lattice vectors.