On chains and Sperner k-families in ranked posets

A ranked poset P has the Sperner property if the sizes of the largest rank and of the largest antichain in P are equal. A natural strengthening of the Sperner property is condition S: For all k, the set of elements of the k largest ranks in P is a Sperner k-family. P satisfies condition T if for all k there exist disjoint chains in P each of which meets the k largest ranks and which covers the kth largest rank. It is proven here that if P satisfies S, it also satisfies T, and that the converse, although in general false, is true for posets with unimodal Whitney numbers. Conditions S and T and the Sperner property are compared here with two other conditions on posets concerning the existence of certain partitions of P into chains.     

AZ-Identities and Strict 2-Part Sperner Properties of Product Posets

One of central issues in extremal set theory is Sperner’s theorem and its generalizations. Among such generalizations is the best-known LYM (also known as BLYM) inequality and the Ahlswede–Zhang (AZ) identity which surprisingly generalizes the BLYM into an identity. Sperner’s theorem and the BLYM inequality has been also generalized to a wide class of posets. Another direction in this research was the study of more part Sperner systems. In this paper we derive AZ type identities for regular posets. We also characterize all maximum 2-part Sperner systems for a wide class of product posets.     

Hamiltonian Cycles and Symmetric Chains in Boolean Lattices

Let B(n) be the subset lattice of \({\{1,2,\dots, n\}.}\) Sperner’s theorem states that the width of B(n) is equal to the size of its biggest level. There have been several elegant proofs of this result, including an approach that shows that B(n) has a symmetric chain partition. Another famous result concerning B(n) is that its cover graph is hamiltonian. Motivated by these ideas and by the Middle Two Levels conjecture, we consider posets that have the Hamiltonian Cycle–Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. We show that the subset lattices have the HC-SCP property, and we obtain this result as a special case of a more general treatment.     

Tropical decomposition of Young’s partition lattice

Young’s partition lattice L(m,n) consists of integer partitions having m parts where each part is at most n. Using methods from complex algebraic geometry, R. Stanley proved that this poset is rank-symmetric, unimodal, and strongly Sperner. Moreover, he conjectured that it has a symmetric chain decomposition, which is a stronger property. Despite many efforts, this conjecture has only been proved for min(m,n)≤4. In this paper, we decompose L(m,n) into level sets for certain tropical polynomials derived from the secant varieties of the rational normal curve in projective space, and we find that the resulting subposets have an elementary raising and lowering algorithm. As a corollary, we obtain a symmetric chain decomposition for the subposet of L(m,n) consisting of “sufficiently generic” partitions.     

Quotients of peck posets

An elementary, self-contained proof of a result of Pouzet and Rosenberg and of Harper is given. This result states that the quotient of certain posets (called unitary Peck) by a finite group of automorphisms retains some nice properties, including the Sperner property. Examples of unitary Peck posets are given, and the techniques developed here are used to prove a result of Lovász on the edge-reconstruction conjecture.Supported in part by a National Science Foundation research grant.     

The Number of Unlabeled Orders on Fourteen Elements

Lacking an explicit formula for the numbers T ₀(n) of all order relations (equivalently: T ₀ topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too.     

Symmetric decompositions and the strong Sperner property for noncrossing partition lattices

We prove that the noncrossing partition lattices associated with the complex reflection groups G(d, d, n) for \(d,n\ge 2\) admit symmetric decompositions into Boolean subposets. As a result, these lattices have the strong Sperner property and their rank-generating polynomials are symmetric, unimodal, and \(\gamma \)-nonnegative. We use computer computations to complete the proof that every noncrossing partition lattice associated with a well-generated complex reflection group is strongly Sperner, thus answering affirmatively a question raised by D. Armstrong.     

Counting finite posets and topologies

A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n11 and all k, and then the numbers of all topologies on n14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 10²³.     

On the stable derivation algebra associated with some braid groups

We shall prove some stability property of the graded Lie algebraD _n of certain derivations associated with pure sphere braid group onn strings; in fact, thatD _n forn≥6. These Lie algebrasD _n are connected with some bigl-adic Galois representations, and the stability property is related to some conjecture of Grothendieck.     

ON 2-ABELIAN (n – 5)-FILIFORM LIE ALGEBRAS

We classify the (n ? 5)-filiform Lie algebras which have the additional property of a non-abelian derived subalgebra. Moreover we show that if a (n ? 5)-filiform Lie algebra is characteristically nilpotent, then it must be 2-abelian.     

On chains and Sperner k-families in ranked posets,II

A ranked poset P satisfies condition S if for all k the set of elements of the k largest ranks in P is a Sperner k-family. It satisfies condition T if for all k there exist disjoint chains in P which each meet the k largest ranks and which cover the kth largest rank. Griggs employed the theory of saturated partitions to prove that if P satisfies S it also satisfies T, and that the converse is true for posets with unimodal Whitney numbers. Here we present new proofs of these facts which do not require the existence of saturated partitions. The first result is proven with a simple network flow argument and the second is proven directly.     

Families of sets with locally bounded width

A family of sets ? islocally k- wide if and only if the width (as a poset ordered by inclusion) of ? is at mostk for everyx. The directed covering graph of a locally 1-wide family of sets is a forest of rooted trees. It is shown that if ? is a locallyk-wide family of subsets of {1,...,n}, then |?|≤(2k) ^k?1 n. The proof involves a counting argument based on families of closed sets associated with theSperner closures in the filters of ?. The Sperner closure ofU in ? is the intersection of the members of the greatest Sperner antichain of ? _U = {V ∈ ?|V ?U}. This closure operation is related to a generalization of maximality in posets.     

Generic Representation Theory of the Unipotent Upper Triangular Groups

It is generally believed (and for the most part it is probably true) that Lie theory, in contrast to the characteristic zero case, is insufficient to tackle the representation theory of algebraic groups over prime characteristic fields. However, in this article we show that, for a large and important class of unipotent algebraic groups (namely the unipotent upper triangular groups U_n), and under a certain hypothesis relating the characteristic p to both n and the dimension d of a representation (specifically, p ≥ max(n, 2d)), Lie theory is completely sufficient to determine the representation theories of these groups. To finish, we mention some important analogies (both functorial and cohomological) between the characteristic zero theories of these groups and their “generic” representation theory in characteristic p.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Multilinear Quantum Lie Operations

It is proved that under an existence condition, the dimension of all n-linear quantum Lie operations lies between (n - 2)! and (n - 1)!; moreover, the low bound is attained if the intersection of all conforming (i.e., satisfying the existence condition) subsets of a given set of quantum variables is nonempty. The upper bound is attained if all subsets are conforming. The space of multilinear quantum Lie operations is almost always generated by symmetric operations. All exceptional cases are given. In particular, the space of general n-linear Lie operations is always generated by general symmetric quantum Lie operations. Bibliography: 24 titles.     

Partition Lattice q-Analogs Related to q-Stirling Numbers

We construct a family of partially ordered sets (posets) that are q-analogs of the set partition lattice. They are different from the q-analogs proposed by Dowling [5]. One of the important features of these posets is that their Whitney numbers of the first and second kind are just the q-Stirling numbers of the first and second kind, respectively. One member of this family [4] can be constructed using an interpretation of Milne [9] for S[n, k] as sequences of lines in a vector space over the Galois field F _q. Another member is constructed so as to mirror the partial order in the subspace lattice.     

Almost sure convergence and bounded entropy

It is shown that the almost sure convergence property for certain sequences of operators {S _n{ implies a uniform bound on the metrical entropy of the sets {S _nf|n=1, 2, ...{, wheref is taken in theL ²-unit ball. This criterion permits one to unify certain counterexamples due to W. Rudin [Ru] and J.M. Marstrand [Mar] and has further applications. The theory of Gaussian processes is crucial in our approach.     

Squarefree P-modules and the cd-index

In this paper, we introduce a new algebraic concept, which we call squarefree P-modules. This concept is inspired from Karu's proof of the non-negativity of the cd-indices of Gorenstein* posets, and supplies a way to study cd-indices from the viewpoint of commutative algebra. Indeed, by using the theory of squarefree P-modules, we give several new algebraic and combinatorial results on CW-posets. First, we define an analogue of the cd-index for any CW-poset and prove its non-negativity when a CW-poset is Cohen–Macaulay. This result proves that the h-vector of the barycentric subdivision of a Cohen–Macaulay regular CW-complex is unimodal. Second, we prove that the Stanley–Reisner ring of the barycentric subdivision of an odd dimensional Cohen–Macaulay polyhedral complex has the weak Lefschetz property. Third, we obtain sharp upper bounds of the cd-indices of Gorenstein* posets for a fixed rank generating function.     

Non-closed Lie subgroups of Lie groups

We obtain several homotopy obstructions to the existence of non-closed connected Lie subgroupsH in a connected Lie groupG.First we show that the foliationF(G, H) onG determined byH is transversely complete [4]; moreover, forK the closure ofH inG, F(K, H) is an abelian Lie foliation [2].Then we prove that ₁(K) and ₁(H) have the same torsion subgroup, _n (K)= _n (H) for alln 2, and rank₁(K) — rank₁(H) > codimF(K, H). This implies, for instance, that a contractible (e.g. simply connected solvable) Lie subgroup of a compact Lie group must be abelian. Also, if rank₁(G) 1 then any connected invariant Lie subgroup ofG is closed; this generalizes a well-known theorem of Mal'cev [3] for simply connected Lie groups.Finally, we show that the results of Van Est on (CA) Lie groups [6], [7] provide many interesting examples of such foliations. Actually, any Lie group with non-compact centre is the (dense) leaf of a foliation defined by a closed 1-form. Conversely, when the centre is compact, the latter is true only for (CA) Lie groups (e.g. nilpotent or semisimple).