Linear extension diameter of subposets of Boolean lattice induced by two levels

The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in exactly one (adjacent) transposition. Recently, Felsner and Massow determined the linear extension diameter of the Boolean lattice B, and they posed a question of determining the linear extension diameter of a subposet of B induced by two levels. We solve the case of the 1st and kth level. The diametral pairs are obtained from minimal vertex covers of so called dependency graphs, a new concept which may be useful also for the general case.     

An extension of Boolean lattice theory

Mathematische Annalen -     

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

Multicolor chain avoidance in the Boolean lattice

Given a collection of colored chain posets, we estimate the number of colored subsets of the Boolean lattice which avoid all chains in the collection. We do this by applying the hypergraph container lemma recursively, with different uniformities at each stage, using a balanced supersaturation result for a certain non-uniform hypergraph encoding forbidden configurations.     

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.     

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

Estimation for the Simple Linear Boolean Model

We consider the simple linear Boolean model, a fundamental coverage process also known as the Markov/General/∞ queue. In the model, line segments of independent and identically distributed length are located at the points of a Poisson process. The segments may overlap, resulting in a pattern of “clumps”–regions of the line that are covered by one or more segments–alternating with uncovered regions or “spacings”. Study and application of the model have been impeded by the difficulty of obtaining the distribution of clump length. We present explicit expressions for the clump length distribution and density functions. The expressions take the form of integral equations, and we develop a method of successive approximation to solve them numerically. Use of the fast Fourier transform greatly enhances the computational efficiency of the method. We further present inference procedures for the model using maximum likelihood techniques. Applications in engineering and biomedicine illustrate the methods.      

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

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.     

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.     

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

The Number of Linear Extensions of the Boolean Lattice

Let L(Q ^t ) denote the number of linear extensions of the t-dimensional Boolean lattice Q ^t . We use the entropy method of Kahn to show that