Computing on-line the lattice of maximal antichains of posets

We consider the on-line computation of the lattice of maximal antichains of a finite poset . This on-line computation satisfies what we call the linear extension hypothesis: the new incoming vertex is always maximal in the current subposet of . In addition to its theoretical interest, this abstraction of the lattice of antichains of a poset has structural properties which give it interesting practical behavior. In particular, the lattice of maximal antichains may be useful for testing distributed computations, for which purpose the lattice of antichains is already widely used. Our on-line algorithm has a run time complexity of , where |P| is the number of elements of the poset, , |MA(P)| is the number of maximal antichains of and (P) is the width of . This is more efficient than the best off-line algorithms known so far.     

Chains,antichains, and complements in infinite partition lattices

We consider the partition lattice \(\Pi (\lambda )\) on any set of transfinite cardinality \(\lambda \) and properties of \(\Pi (\lambda )\) whose analogues do not hold for finite cardinalities. Assuming AC, we prove: (I) the cardinality of any maximal well-ordered chain is always exactly \(\lambda \); (II) there are maximal chains in \(\Pi (\lambda )\) of cardinality \(> \lambda \); (III) a regular cardinal \(\lambda \) is strongly inaccessible if and only if every maximal chain in \(\Pi (\lambda )\) has size at least \(\lambda \); if \(\lambda \) is a singular cardinal and \(\mu ^{< \kappa } < \lambda \le \mu ^\kappa \) for some cardinals \(\kappa \) and (possibly finite) \(\mu \), then there is a maximal chain of size \(< \lambda \) in \(\Pi (\lambda )\); (IV) every non-trivial maximal antichain in \(\Pi (\lambda )\) has cardinality between \(\lambda \) and \(2^{\lambda }\), and these bounds are realised. Moreover, there are maximal antichains of cardinality \(\max (\lambda , 2^{\kappa })\) for any \(\kappa \le \lambda \); (V) all cardinals of the form \(\lambda ^\kappa \) with \(0 \le \kappa \le \lambda \) occur as the cardinalities of sets of complements to some partition \(\mathcal {P} \in \Pi (\lambda )\), and only these cardinalities appear. Moreover, we give a direct formula for the number of complements to a given partition. Under the GCH, the cardinalities of maximal chains, maximal antichains, and numbers of complements are fully determined, and we provide a complete characterisation.     

Filters in the partition lattice

Given a filter \(\Delta \) in the poset of compositions of n, we form the filter \(\Pi ^{*}_{\Delta }\) in the partition lattice. We determine all the reduced homology groups of the order complex of \(\Pi ^{*}_{\Delta }\) as \({\mathfrak S}_{n-1}\)-modules in terms of the reduced homology groups of the simplicial complex \(\Delta \) and in terms of Specht modules of border shapes. We also obtain the homotopy type of this order complex. These results generalize work of Calderbank–Hanlon–Robinson and Wachs on the d-divisible partition lattice. Our main theorem applies to a plethora of examples, including filters associated with integer knapsack partitions and filters generated by all partitions having block sizes a or b. We also obtain the reduced homology groups of the filter generated by all partitions having block sizes belonging to the arithmetic progression \(a, a + d, \ldots , a + (a-1) \cdot d\), extending work of Browdy.     

Every finite lattice can be embedded in a finite partition lattice

Conclusions There are many questions, which arise in connection with the theorem presented. In general, we would like to know more about the class of embeddings of a given lattice in the lattices of all equivalences over finite sets. Some of these problems are studied in [4]. In this paper, an embedding is called normal, if it preserves 0 and 1. Using regraphs, our result can be easily improved as follows: THEOREM.For every lattice L, there exists a positive integer n ₀,such that for every n≥n ₀,there is a normal embedding π: L→Eq(A), where |A|=n. Embedding satisfying special properties are shown in Lemma 3.2 and Basic Lemma 6.2. We hope that our method of regraph powers will produce other interesting results. There is also a question about the effectiveness of finding an embedding of a given lattice. In particular, the proof presented here cannot be directly used to solve the following. Problem. Can the dual of Eq(4) be embedded into Eq(2¹⁰⁰⁰)? Presented by G. Gr?tzer.     

A basis for the non-crossing partition lattice top homology

We find a basis for the top homology of the non-crossing partition lattice T _n . Though T _n is not a geometric lattice, we are able to adapt techniques of Björner (A. Björner, On the homology of geometric lattices. Algebra Universalis 14 (1982), no. 1, 107–128) to find a basis with C _n?1 elements that are in bijection with binary trees. Then we analyze the action of the dihedral group on this basis.     

Embedded antichains in tournaments

The maximum antichain cardinality (MACC) of a tournament is the maximum number of incomparable subtournaments of T. We establish some properties of MACC. We describe all tournaments whose MACC is 1 or 2, show that MACC can grow exponentially with the size of the vertex set of a tournament, and present some questions for further investigation.     

Infinite antichains in semilattices

In this paper we consider infinite antichains and the semilattices that they generate, mainly in the context of continuous semilattices. Conditions are first considered that lead to the antichain generating a copy of a countable product of the two-element semilattice. Then a special semilattice, called , is defined, its basic properties developed, and it is shown in our main result that a continuous semilattice with an infinite antichain converging to a larger element contains a semilattice copy of . The paper closes with a consideration of countable antichains that converge to a lower element or a parallel element and the kinds of semilattices generated in this context.The first two authors gratefully acknowledge the partial support of the National Science Foundation and the hospitality of Oxford University during the preparation of this paper.     

On canonical antichains

An antichain A of a well-founded quasi-order Q is canonical if for every ideal F of Q, F has an infinite antichain if and only if F∩A is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation.     

Diamond and antichains

It is obvious that implies the existence of an antichain of stationary sets of cardinality which is the largest possible cardinality. We show that the obvious antichain is not maximal and find a less obvious extension of it by ₂ more stationary sets.Mathematics Subject Classification (2000): 03EThe research of the authors is partially supported by the NSF.The second author was partially supported by IHES during his June 5–25, 2002, visit. He thanks Stevo Todorcevic and Boban Velickovic for conversations during the visit on the main question answered in this report.     

Maximum antichains in the product of chains

Let P be the poset k ₁ × ... × k _n , which is a product of chains, where n1 and k ₁ ... k _n 2. Let . P is known to have the Sperner property, which means that its maximum ranks are maximum antichains. Here we prove that its maximum ranks are its only maximum antichains if and only if either n=1 or M1. This is a generalization of a classical result, Sperner's Theorem, which is the case k ₁= ... =k _n =2. We also determine the number and location of the maximum ranks of P.Research supported in part by the National Science Foundation 10/25/83.     

Strongly maximal antichains in posets

Given a collection S of sets, a set S∈S is said to be strongly maximal in S if |T?S|≤|S?T| for every T∈S. In Aharoni (1991) [3] it was shown that a poset with no infinite chain must contain a strongly maximal antichain. In this paper we show that for countable posets it suffices to demand that the poset does not contain a copy of posets of two types: a binary tree (going up or down) or a “pyramid”. The latter is a poset consisting of disjoint antichains A_i,i=1,2,…, such that |A_i|=i and x<y whenever x∈A_i,y∈A_j and j<i (a “downward” pyramid), or x<y whenever x∈A_i,y∈A_j and i<j (an “upward” pyramid).     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

On the existence of regular antichains

A $k$-regular antichain in the Boolean lattice of subsets is one in which each point occurs in exactly $k$ sets. The existence and construction of $k$-regular antichains on $m$ points for each positive integer pair $(k,m)$ is determined for all $m$ and most $k$.     

Large deviations in the geometry of convex lattice polygons

We provide a full large deviation principle (LDP) for the uniform measure on certain ensembles of convex lattice polygons. This LDP provides for the analysis of concentration of the measure on convex closed curves. In particular, convergence to a limiting shape results in some particular cases, including convergence to a circle when the ensemble is defined as those centered convex polygons, with vertices on a scaled two dimensional lattice, and with length bounded by a constant. The Gauss-Minkowskii transform of convex curves plays a crucial role in our approach. Partially supported by grants ININS 94-3420 and RFF1-96-01-00676. Partially supported by a US-Israel BSF grant and by the fund for promotion of research at the Technion.     

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 .