Peeling phylogenetic ‘oranges’

We investigate the combinatorics of a topological space that is generated by the set of edge-weighted finite trees. This space arises by multiplying the weights of edges on paths in trees and is closely connected to tree reconstruction problems involving finite state Markov processes. We show that this space is a contractible finite CW-complex whose face poset can be described via a partial order on semilabelled forests. We then describe some combinatorial properties of this poset, showing that, for example, it is pure, thin and contractible.     

The dimension of planar posets

A partially ordered set (poset) is planar if it has a planar Hasse diagram. The dimension of a bounded planar poset is at most two. We show that the dimension of a planar poset having a greatest lower bound is at most three. We also construct four-dimensional planar posets, but no planar poset with dimension larger than four is known. A poset is called a tree if its Hasse diagram is a tree in the graph-theoretic sense. We show that the dimension of a tree is at most three and give a forbidden subposet characterization of two-dimensional trees.     

Reconstructing the orbit type stratification of a torus action from its equivariant cohomology

We investigate what information on the orbit type stratification of a torus action on a compact space is contained in its rational equivariant cohomology algebra. Regarding the (labelled) poset structure of the stratification, we show that equivariant cohomology encodes the subposet of ramified elements. For equivariantly formal actions, we also examine what cohomological information of the stratification is encoded. In the smooth setting, we show that under certain conditions—which in particular hold for a compact orientable manifold with discrete fixed point set—the equivariant cohomologies of the strata are encoded in the equivariant cohomology of the manifold.

     

Order series of labelled posets

Order series of labelled posets are multi-analogues of the more familiar order polynomials; the corresponding multi-analogues of the related representation polynomials are calledE-series. These series can be used to describe the effect of composition of labelled posets on their order polynomials, whence their interest for us. We give a reciprocity theorem forE-series, and show that for an unlabelled poset the form of theE-series depends only upon the comparability graph of the poset. We also prove that theE-series of any labelled poset is a rational power series (in many indeterminates) and give an algorithm for computing it which runs in polynomial time when the poset is strictly labelled and of bounded width. Finally, we give an explicit product formula for theE-series of strictly labelled interval posets.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant #0105392.     

Hyperplane arrangements with a lattice of regions

A hyperplane arrangement is a finite set of hyperplanes through the origin in a finite-dimensional real vector space. Such an arrangement divides the vector space into a finite set of regions. Every such region determines a partial order on the set of all regions in which these are ordered according to their combinatorial distance from the fixed base region.We show that the base region is simplicial whenever the poset of regions is a lattice and that conversely this condition is sufficient for the lattice property for three-dimensional arrangements, but not in higher dimensions. For simplicial arrangements, the poset of regions is always a lattice.In the case of supersolvable arrangements (arrangements for which the lattice of intersections of hyperplanes is supersolvable), the poset of regions is a lattice if the base region is suitably chosen. We describe the geometric structure of such arrangements and derive an expression for the rank-generating function similar to a known one for Coxeter arrangements. For arrangements with a lattice of regions we give a geometric interpretation of the lattice property in terms of a closure operator defined on the set of hyperplanes.The results generalize to oriented matroids. We show that the adjacency graph (and poset of regions) of an arrangement determines the associated oriented matroid and hence in particular the lattice of intersections.The work of Anders Björner was supported in part by a grant from the NSF. Paul Edelman's work was supported in part by NSF Grants DMS-8612446 and DMS-8700995. The work of Günter Ziegler was done while he held a Norman Levinson Graduate Fellowship at MIT.     

A category of quantum posets

We investigate a category of quantum posets that generalizes the category of posets and monotone functions. Up to equivalence, its objects are hereditarily atomic von Neumann algebras equipped with quantum partial orders in Weaver’s sense. We show that this category is complete, cocomplete and symmetric monoidal closed. As a consequence, any discrete quantum family of maps from a discrete quantum space to a partially ordered set is canonically equipped with a quantum preorder. In particular, the quantum power set of a quantum set is canonically a quantum poset. We show that each quantum poset embeds into its quantum power set in complete analogy with the classical case.     

Combinatorics of Thin Posets: Application to Monotone Covering Properties

A class of posets, called thin posets, is introduced, and it is shown that every thin poset can be covered by a finite family of trees. This fact is used to show that (within ZFC) every separable monotonically Menger space is first countable. This contrasts with the previously known fact that under CH there are countable monotonically Lindelöf spaces which are not first countable.     

Decompositions in Quantum Logic

We present a method of constructing an orthomodular poset from a relation algebra. This technique is used to show that the decompositions of any algebraic, topological, or relational structure naturally form an orthomodular poset, thereby explaining the source of orthomodularity in the ortholattice of closed subspaces of a Hilbert space. Several known methods of producing orthomodular posets are shown to be special cases of this result. These include the construction of an orthomodular poset from a modular lattice and the construction of an orthomodular poset from the idempotents of a ring.

Particular attention is paid to decompositions of groups and modules. We develop the notion of a norm on a group with operators and of a projection on such a normed group. We show that the projections of a normed group with operators form an orthomodular poset with a full set of states. If the group is abelian and complete under the metric induced by the norm, the projections form a -complete orthomodular poset with a full set of countably additive states.

We also describe some properties special to those orthomodular posets constructed from relation algebras. These properties are used to give an example of an orthomodular poset which cannot be embedded into such a relational orthomodular poset, or into an orthomodular lattice. It had previously been an open question whether every orthomodular poset could be embedded into an orthomodular lattice.

     

Toric cubes

A toric cube is a subset of the standard cube defined by binomial inequalities. These basic semialgebraic sets are precisely the images of standard cubes under monomial maps. We study toric cubes from the perspective of topological combinatorics. Explicit decompositions as CW-complexes are constructed. Their open cells are interiors of toric cubes and their boundaries are subcomplexes. The motivating example of a toric cube is the edge-product space in phylogenetics, and our work generalizes results known for that space.     

Poset extensions, convex sets, and semilattice presentations

The paper is devoted to an algebraic and geometric study of the feasible set of a poset, the set of finite probability distributions on the elements of the poset whose weights satisfy the order relationships specified by the poset. For a general poset, this feasible set is a barycentric algebra. The feasible sets of the order structures on a given finite set are precisely the convex unions of the primary simplices, the facets of the first barycentric subdivision of the simplex spanned by the elements of the set. As another fragment of a potential complete duality theory for barycentric algebras, a duality is established between order-preserving mappings and embeddings of feasible sets. In particular, the primary simplices constituting the feasible set of a given finite poset are the feasible sets of the linear extensions of the poset. A finite poset is connected if and only if its barycentre is an extreme point of its feasible set. The feasible set of a (general) disconnected poset is the join of the feasible sets of its components. The extreme points of the feasible set of a finite poset are specified in terms of the disjointly irreducible elements of the semilattice presented by the poset. Semilattices presented by posets are characterised in terms of various distributivity concepts.     

On a Subposet of the Tamari Lattice

We explore some of the properties of a subposet of the Tamari lattice introduced by Pallo, which we call the comb poset. We show that a number of binary functions that are not well-behaved in the Tamari lattice are remarkably well-behaved within an interval of the comb poset: rotation distance, meets and joins, and the common parse words function for a pair of trees. We relate this poset to a partial order on the symmetric group studied by Edelman.     

Order Environments of Topological Spaces

In this paper it is proved that a space may be realized as the set of the maximal elements in a continuous poset if and only if it is Tychonoff.     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.     

On a poset of trees

We will prove that the path minimizes the number of closed walks of length ℓ among the connected graphs for all ℓ. Indeed, we will prove that the number of closed walks of length ℓ and many other properties such as the spectral radius, Estada index increase or decrease along a certain poset of trees. This poset is a leveled poset with path as the smallest element and star as the greatest element.     

A cohomological characteristic for the length and width of a partially ordered set

Grothendieck topologies on a poset preset by one set and corresponding sheaf cohomologies are analyzed. The relation between the given cohomologies and the length of a poset is identified. For this purpose, Grothendieck topologies are defined on the set of the chains and antichains of the given poset; the corresponding theories of sheaf cohomologies are formed and with the help of those the poset is analyzed.     

The rank-generating functions of upho posets

Upper homogeneous finite type (upho) posets are a large class of partially ordered sets with the property that the principal order filter at every vertex is isomorphic to the whole poset. Well-known examples include k-ary trees, the grid graphs, and the Stern poset. Very little is known about upho posets in general. In this paper, we construct upho posets with Schur-positive Ehrenborg quasisymmetric functions, whose rank-generating functions have rational poles and zeros. We also categorize the rank-generating functions of all planar upho posets. Finally, we prove the existence of an upho poset with an uncomputable rank-generating function.     

The lumpability property for a family of Markov chains on poset block structures

We construct different classes of lumpings for a family of Markov chain products which reflect the structure of a given finite poset. We essentially use combinatorial methods. We prove that, for such a product, every lumping can be obtained from the action of a suitable subgroup of the generalized wreath product of symmetric groups, acting on the underlying poset block structure, if and only if the poset defining the Markov process is totally ordered, and one takes the uniform Markov operator in each factor state space. Finally we show that, when the state space is a homogeneous space associated with a Gelfand pair, the spectral analysis of the corresponding lumped Markov chain is completely determined by the decomposition of the group action into irreducible submodules.     

A self paired Hopf algebra on double posets and a Littlewood-Richardson rule

Let D be the set of isomorphism types of finite double partially ordered sets, that is sets endowed with two partial orders. On ZD we define a product and a coproduct, together with an internal product, that is, degree-preserving. With these operations ZD is a Hopf algebra. We define a symmetric bilinear form on this Hopf algebra: it counts the number of pictures (in the sense of Zelevinsky) between two double posets. This form is a Hopf pairing, which means that product and coproduct are adjoint each to another. The product and coproduct correspond respectively to disjoint union of posets and to a natural decomposition of a poset into order ideals. Restricting to special double posets (meaning that the second order is total), we obtain a notion equivalent to Stanley's labelled posets, and a Hopf subalgebra already considered by Blessenohl and Schocker. The mapping which maps each double poset onto the sum of the linear extensions of its first order, identified via its second (total) order with permutations, is a Hopf algebra homomorphism, which is isometric and preserves the internal product, onto the Hopf algebra of permutations, previously considered by the two authors. Finally, the scalar product between any special double poset and double posets naturally associated to integer partitions is described by an extension of the Littlewood-Richardson rule.     

Geometry of the Space of Phylogenetic Trees

We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of trees. This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.     

Going down in (semi)lattices of finite moore families and convex geometries

In this paper we first study what changes occur in the posets of irreducible elements when one goes from an arbitrary Moore family (respectively, a convex geometry) to one of its lower covers in the lattice of all Moore families (respectively, in the semilattice of all convex geometries) defined on a finite set. Then we study the set of all convex geometries which have the same poset of join-irreducible elements. We show that this set—ordered by set inclusion—is a ranked join-semilattice and we characterize its cover relation. We prove that the lattice of all ideals of a given poset P is the only convex geometry having a poset of join-irreducible elements isomorphic to P if and only if the width of P is less than 3. Finally, we give an algorithm for computing all convex geometries having the same poset of join-irreducible elements.