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.     

Wide posets with fixed height and cutset number

Given an element x of a partial order P, a set S P is said to be a cutset for x if S x meets every maximal chain of P and x is incomparable to every element of S. The cutset number of P is the minimum m such that every element of P has a cutset of size at most m. Let w(m, h) be the maximum width of a poset with height h and cutset number m. We determine the order of growth of w(m, h) for fixed m or fixed h: w(m, h)(h ^m/2) for fixed m and w(m, h)(m ^h) for fixed h.Research supported in part by ONR Grant N00014-85K0570 and by NSA/MSP Grant MDA904-90-H-4011.     

Finite cutsets and finite antichains

An ordered set (P,) has the m cutset property if for each x there is a set Fx with cardinality less than m, such that each element of Fx is incomparable to x and {x} Fx meets every maximal chain of (P,). Let n be least, such that each element x of any P having the m cutset property belongs to some maximal antichain of cardinality less than n. We specify n for m < w. Indeed, n-1=m= width P for m=1,2,n=5 if m=3 and n₁ if m 4. With the added hypothesis that every bounded chain has a supremum and infimum in P, it is shown that for 4m₀, n=₀. That is, if each element x has a finite cutset Fx, each element belongs to a finite maximal antichain.This work was supported by the NSERC of Canada.     

Sublattices of complete lattices with continuity conditions

Various embedding problems of lattices into complete lattices are solved. We prove that for any join-semilattice S with the minimal join-cover refinement property, the ideal lattice Id S of S is both algebraic and dually algebraic. Furthermore, if there are no infinite D-sequences in J(S), then Id S can be embedded into a direct product of finite lower bounded lattices. We also find a system of infinitary identities that characterize sublattices of complete, lower continuous, and join-semidistributive lattices. These conditions are satisfied by any (not necessarily finitely generated) lower bounded lattice and by any locally finite, join-semidistributive lattice. Furthermore, they imply M. Erné’s dual staircase distributivity.On the other hand, we prove that the subspace lattice of any infinite-dimensional vector space cannot be embedded into any ℵ₀-complete, ℵ₀-upper continuous, and ℵ₀-lower continuous lattice. A similar result holds for the lattice of all order-convex subsets of any infinite chain.Dedicated to the memory of Ivan RivalReceived April 4, 2003; accepted in final form June 16, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

The Menger property for infinite ordered sets

It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M (P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M (P) does not have a cutset of size <x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

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 intersection theorems

LetL(A) be the set of submatrices of anm×n matrixA. ThenL(A) is a ranked poset with respect to the inclusion, and the poset rank of a submatrix is the sum of the number of rows and columns minus 1, the rank of the empty matrix is zero. We attack the question: What is the maximum number of submatrices such that any two of them have intersection of rank at leastt? We have a solution fort=1,2 using the followoing theorem of independent interest. Letm(n,i,j,k) = max(|F|;|G|), where maximum is taken for all possible pairs of families of subsets of ann-element set such thatF isi-intersecting,G isj-intersecting andF ansd,G are cross-k-intersecting. Then fori≤j≤k, m(n,i,j,k) is attained ifF is a maximali-intersecting family containing subsets of size at leastn/2, andG is a maximal2k?i-intersecting family. Furthermore, we discuss and Erd?s-Ko-Rado-type question forL(A), as well.     

Schubert unions in Grassmann varieties

We study subsets of Grassmann varieties G(l,m) over a field F, such that these subsets are unions of Schubert cycles, with respect to a fixed flag. We study unions of Schubert cycles of Grassmann varieties G(l,m) over a field F. We compute their linear span and, in positive characteristic, their number of F_q-rational points. Moreover, we study a geometric duality of such unions, and give a combinatorial interpretation of this duality. We discuss the maximum number of F_q-rational points for Schubert unions of a given spanning dimension, and as an application to coding theory, we study the parameters and support weights of the well-known Grassmann codes. Moreover, we determine the maximum Krull dimension of components in the intersection of G(l,m) and a linear space of given dimension in the Plücker space.     

Primes,irreducibles and extremal lattices

This paper studies certain types of join and meet-irreducibles called coprimes and primes. These elements can be used to characterize certain types of lattices. For example, a lattice is distributive if and only if every join-irreducible is coprime. Similarly, a lattice is meet-pseudocomplemented if and only if each atom is coprime. Furthermore, these elements naturally decompose lattices into sublattices so that often properties of the original lattice can be deduced from properties of the sublattice. Not every lattice has primes and coprimes. This paper shows that lattices which are long enough must have primes and coprimes and that these elements and the resulting decompositions can be used to study such lattices.The length of every finite lattice is bounded above by the minimum of the number of meet-irreducibles (meet-rank) and the number of join-irreducibles (join-rank) that it has. This paper studies lattices for which length=join-rank or length=meet-rank. These are called p-extremal lattices and they have interesting decompositions and properties. For example, ranked, p-extremal lattices are either lower locally distributive (join-rank=length), upper locally distributive (meet-rank=length) or distributive (join-rank=meet-rank=length). In the absence of the Jordan-Dedekind chain condition, p-extremal lattices still have many interesting properties. Of special interest are the lattices that satisfy both equalities. Such lattices are called extremal; this class includes distributive lattices and the associativity lattices of Tamari. Even though they have interesting decompositions, extremal lattices cannot be characterized algebraically since any finite lattice can be embedded as a subinterval into an extremal lattice. This paper shows how prime and coprime elements, and the poset of irreducibles can be used to analyze p-extremal and other types of lattices.The results presented in this paper are used to deduce many key properties of the Tamari lattices. These lattices behave much like distributive lattices even though they violate the Jordan-Dedekind chain condition very strongly having maximal chains that vary in length from N-1 to N(N-1)/2 where N is a parameter used in the construction of these lattices.     

The PT-order,minimal cutsets and menger property

If P is a poset, the associated PT-order is the quasi order in which a b holds if every maximal chain of P which passes through a also passes through b. P is special if whenever A is a chain in P and a=sup A or inf A, then there is b A such that b a. It is proved that if P is chain complete and special then the set of -maximal elements is -dominating and contains a minimal cutset. As corollaries of this, we give partial answers to (i) a question of Rival and Zaguia by showing that if P is regular and special every element is in a minimal cutset and (ii) a question of Brochet and Pouzet by showing that if P is chain complete and special then it has the Menger property.Research partially supported by grants from the National Natural Science Foundation of China and the Natural Science Foundation of Shaanxi province     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

Towards an axiomatization of orderings

A set of six axioms for sets of relations is introduced. All well-known sets of specific orderings, such as linear and weak orderings, satisfy these axioms. These axioms impose criteria of closedness with respect to several operations, such as concatenation, substitution and restriction. For operational reasons and in order to link our results with the literature, it is shown that specific generalizations of the transitivity condition give rise to sets of relations which satisfy these axioms. Next we study minimal extensions of a given set of relations which satisfy the axioms. By this study we come to the fundamentals of orderings: They appear to be special arrangements of several types of disorder. Finally we notice that in this framework many new sets of relations have to be regarded as a set of orderings and that it is not evident how to minimize the number of these new sets of orderings.Symbol Table U universe (infinite countable) - D set of possible domains (finite and non-empty subsets of U) - R set of all considered relations - A empty relation on A - Id A identity relation on A - All A all relation on A - c complement operator (see Definition 2.1) - v converse operator (see Definition 2.1) - s symmetric part (see Definition 2.1) - asymmetric part (see Definition 2.1) - n non-diagonal part (see Definition 2.1) - r reflexive closure (see Definition 2.1) We gratefully acknowledge the support by the Co-operation Centre of Tilburg and Eindhoven Universities.     

Uniform binary geometries

In a geometric lattice every interval can be mapped isomorphically into an upper interval (containing 1) by a strong map. A natural question thus arises as to what extent certain assumptions on the upper interval structure determine the whole lattice. We consider conditions of the following sort: that above a certain levelm any two upper intervals of the same length be isomorphic. This property, called uniformity, is studied for binary geometries. The geometries satisfying the strongest uniformity condition (m = 1) are determined (except for one open case). As is to be expected the corresponding problem for lower intervals is easier and is solved completely.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

A sperner-type theorem

Let P=P ₁×P ₂×...×P _M be the direct product of symmetric chain orders P ₁, P ₂, ..., P _M . Let F be a subset of P containing no l+1 elements which are identical in M–1 components and linearly ordered in the Mth one. Then max |F|cM ^1/2lW(P), where W(P) is the cardinality of the largest level of P, and c is independent of P, M and l. Infinitely many P show that this result is best possible for every M and l apart from the constant factor c.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

Balancing poset extensions

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log₂ e (X) comparisons whereC is approximately 2.17.Supported in part by NSF Grant MCS83-01867.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.