Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Partitioning Boolean lattices into antichains

Let f(n) be the smallest integer t such that a poset obtained from a Boolean lattice with n atoms by deleting both the largest and the smallest elements can be partitioned into t antichains of the same size except for possibly one antichain of a smaller size. In this paper, it is shown that f(n)b n²/log n. This is an improvement of the best previously known upper bound for f(n).     

Intersecting antichains and shadows in linear lattices

We establish a homomorphism of finite linear lattices onto the Boolean lattices via a group acting on linear lattices. By using this homomorphism we prove the intersecting antichains in finite linear lattices satisfy an LYM-type inequality, as conjectured by Erd?s, Faigle and Kern, and we state a Kruskal-Katona type theorem for the linear lattices.     

Large antichains in the partition lattice

Consider the partially ordered set of all partitions of an n-element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. We show that the ratio of the size of the largest antichain to the size of the largest rank exceeds n^1/35 for all n sufficiently large.     

On maximal antichains consisting of sets and their complements

Let 1 ? k₁ ? k₂ ? … ? k_n be integers and let S denote the set of all vectors x = (x₁, x₂, …, x_n) with integral coordinates satisfying 0 ? x_i ? k_i, i = 1, 2, …, n. The complement of x is (k₁ ? x₁, k₂ ? x₂, …, k_n ? x_n) and a subset X of S is an antichain provided that for any two distinct elements x, y of X, the inequalities x_i ? y_i, i = 1, 2, …, n, do not all hold. We determine an LYM inequality and the maximal cardinality of an antichain consisting of vectors and its complements. Also a generalization of the Erdös-Ko-Rado theorem is given.     

On infinite additive complements

Two infinite sequences A and B of non-negative integers are called infinite additive complements if their sum contains all sufficiently large integers. For a sequence T of non-negative integers, let T(x) be the number of terms of T not exceeding x. In 1994, S′ark¨ozy and Szemer′edi confirmed a conjecture of Danzer by proving that, for infinite additive complements A and B, if lim sup A(x)B(x)/x 1, then A(x)B(x)-x → +∞ as x → +∞. In this paper, it is proved that, if A and B are infinite additive complements with lim sup A(x)B(x)/x(4 2～(1/2) + 2)/7 = 1.093 …, then(A(x)B(x)-x)/min{A(x), B(x)} → +∞ as x → +∞.     

Fixed points and complements in finite lattices

Let L be a finite lattice and . Suppose that B is a set of lower semicomplements of x, which includes all complements of x. We show that the partially ordered set has the fixed point property.     

On complements in lattices with covering properties

Dedicated to the memory of Herbert Gross     

Shellability of noncrossing partition lattices

We give a case-free proof that the lattice of noncrossing partitions associated to any finite real reflection group is EL-shellable. Shellability of these lattices was open for the groups of type and those of exceptional type and rank at least three.

     

Tight embedding of modular lattices into partition lattices: progress and program

A famous Theorem of Pudlak and T?ma states that each finite lattice L occurs as sublattice of a finite partition lattice. Here we derive, for modular lattices L, necessary and sufficient conditions for cover-preserving embeddability. Aspects of our work relate to Bjarni Jónsson.     

Dynamics of systems on infinite lattices

The dynamics of infinite-dimensional lattice systems is studied. A necessary and sufficient condition for asymptotic compactness of lattice dynamical systems is introduced. It is shown that a lattice system has a global attractor if and only if it has a bounded absorbing set and is asymptotically null. As an application, it is proved that the lattice reaction-diffusion equation has a global attractor in a weighted l² space, which is compact as well as contains traveling waves. The upper semicontinuity of global attractors is also obtained when the lattice reaction-diffusion equation is approached by finite-dimensional systems.     

Non-crossing partition lattices in finite real reflection groups

For a finite real reflection group with Coxeter element we give a case-free proof that the closed interval, , forms a lattice in the partial order on induced by reflection length. Key to this is the construction of an isomorphic lattice of spherical simplicial complexes. We also prove that the greatest element in this latter lattice embeds in the type simplicial generalised associahedron, and we use this fact to give a new proof that the geometric realisation of this associahedron is a sphere.

     

Formality of the complements of subspace arrangements with geometric lattices

We show that for an arrangement of subspaces in a complex vector space with geometric intersection lattice, the complement of the arrangement is formal. We prove that the Morgan rational model for such an arrangement complement is formal as a differential graded algebra. Bibliography: 10 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 235–247.