The Bruhat Order on the Involutions of the Symmetric Group

In this paper we study the partially ordered set of the involutions of the symmetric group S _n with the order induced by the Bruhat order of S _n. We prove that this is a graded poset, with rank function given by the average of the number of inversions and the number of excedances, and that it is lexicographically shellable, hence Cohen-Macaulay, and Eulerian.     

Algebras Defined from Ordered Sets and the Varieties they Generate

We investigate ways of representing ordered sets as algebras and how the order relation is reflected in the algebraic properties of the variety (equational class) generated by these algebras. In particular we consider two different but related methods for constructing an algebra with one binary operation from an arbitrary ordered set with a top element. The two varieties generated by all these algebras are shown to be well-behaved in that they are locally finite, finitely based, and have an equationally definable order relation. We exhibit a bijection between the subdirectly irreducible algebras in each variety and the class of all ordered sets with top element. We determine the structure and cardinality of the free algebra on n-free generators and provide sharp bounds on the number of n-generated algebras in each variety. These enumeration results involve the number of quasi-orders on an n-element set.     

Shelling the coset poset

It is shown that the coset lattice of a finite group has shellable order complex if and only if the group is complemented. Furthermore, the coset lattice is shown to have a Cohen-Macaulay order complex in exactly the same conditions. The group theoretical tools used are relatively elementary, and avoid the classification of finite simple groups and of minimal finite simple groups.     

Basic Interval Orders

An interval order of length n has elements in correspondence with a collection of intervals in the linearly ordered set {1, 2, ..., n}. A basic interval order of length n has the property that removal of any element yields an order with length less than n. We construct and enumerate the set of basic length n interval orders.     

On the Lattice of Antichains of Finite Intervals

Motivated by applications to information retrieval, we study the lattice of antichains of finite intervals of a locally finite, totally ordered set. Intervals are ordered by reverse inclusion; the order between antichains is induced by the lower set they generate. We discuss in general properties of such antichain completions; in particular, their connection with Alexandrov completions. We prove the existence of a unique, irredundant ∧-representation by ∧-irreducible elements, which makes it possible to write the relative pseudo-complement in closed form. We also discuss in detail properties of additional interesting operators used in information retrieval. Finally, we give a formula for the rank of an element and for the height of the lattice.     

Partial Orders on Weak Orders Convex Subsets

We study a visibility relation on the nonempty connected convex subsets of a finite partially ordered set and we investigate the partial orders representable as a visibility relation of such subsets of a weak order. Moreover, we consider restrictions where the subsets of the weak order are total orders or isomorphic total orders.     

The combinatorics of twisted involutions in Coxeter groups

The open intervals in the Bruhat order on twisted involutions in a Coxeter group are shown to be PL spheres. This implies results conjectured by F. Incitti and sharpens the known fact that these posets are Gorenstein over .

We also introduce a Boolean cell complex which is an analogue for twisted involutions of the Coxeter complex. Several classical Coxeter complex properties are shared by our complex. When the group is finite, it is a shellable sphere, shelling orders being given by the linear extensions of the weak order on twisted involutions. Furthermore, the -polynomial of the complex coincides with the polynomial counting twisted involutions by descents. In particular, this gives a type-independent proof that the latter is symmetric.

     

On the poset of conjugacy classes of subgroups of π-power index

We investigate tile poset S^π(G)/G of conjugacy clases of subgroups of π-power index in a finite group G. In particular, we are concerned with combinatorial and topological properties of the order complex of S^π(G)/G. We show that the order complex of S^π(G)/G iS homotopic to a join of orbit spaces of order complexes of posets, which bear structural information on the cheif factors of the group. Moreover, for π-solvable groups and in case π = {p} we reveal a shellable subposer of S^π(G)/G of the same homotopy type. This complements the study of the poset S^π(G) of subgroups of π-power index performed in [20]. For the analysis of the order complexes we develop some new lemmata on the topology of order complexes of posets and in the theory of shellability.     

Interval orders based on weak orders

One definition of an interval order is as an order isomorphic to that of a family of nontrivial intervals of a linearly ordered set with [a,b] < [c,d] if b c. Fishburn's theorem states that an order is an interval order if and only if it has no four-element restriction isomorphic to the ordered set (shown in Fig. 1) “ ”. We show that an order is isomorphic to a family of nontrivial intervals of a weak order, ordered as above, if and only if it has no restriction to one of the four ordered sets (shown in Fig. 2) “ ”, a six-element crown or a six-element fence.     

A Finite Non-Unit Free Triangle Order

The notion of a free triangle representation of a partially ordered set was first introduced by Josh Laison [4] as a generalization of the ideas of interval and trapezoid representations. A free triangle representation assigns a triangle to each element of a partially ordered set, with all triangles having one vertex on each of two parallel baselines and a third ‘free’ vertex between the two baselines. In a previous paper [1] we presented an example of an infinite non-unit free triangle order. In this paper we use some of the same ideas to construct an example of a finite, albeit more complicated, non-unit free triangle order.The majority of the content in this paper (theorems, proofs, etc.) was prepared before Ken's untimely death in March of 2005.     

Shelling pseudopolyhedra

The notion of shellability originated in the context of polyhedral complexes and combinatorial topology. An abstraction of this concept for graded posets (i.e., graded partially ordered sets) was recently introduced by Björner and Wachs first in the finite case [1] and then with Walker in the infinite case [11]. Many posets arising in combinatorics and in convex geometry were investigated and some proved to be shellable. A key achievement was the proof by Bruggesser and Mani that boundary complexes of convex polytopes are shellable [4].We extend here the result of Bruggesser and Mani to polyhedral complexes arising as boundary complexes of more general convex sets, called pseudopolyhedra, with suitable asymptotic behavior. This includes a previous result on tilings of a Euclidean space ^d which are projections of the boundary of a (d+1)-pseudopolyhedron [7].     

Evidential reasoning in large partially ordered sets

The Dempster-Shafer theory of belief functions has proved to be a powerful formalism for uncertain reasoning. However, belief functions on a finite frame of discernment Ω are usually defined in the power set 2^Ω, resulting in exponential complexity of the operations involved in this framework, such as combination rules. When Ω is linearly ordered, a usual trick is to work only with intervals, which drastically reduces the complexity of calculations. In this paper, we show that this trick can be extrapolated to frames endowed with an arbitrary lattice structure, not necessarily a linear order. This principle makes it possible to apply the Dempster-Shafer framework to very large frames such as the power set, the set of partitions, or the set of preorders of a finite set. Applications to multi-label classification, ensemble clustering and preference aggregation are demonstrated.     

Tchebyshev Posets

We construct for each $n$ an Eulerian partially ordered set $T_n$ of rank $n+1$ whose $ce$-index provides a non-commutative generalization of the $n$th Tchebyshev polynomial. We show that the order complex of each $T_n$ is shellable, homeomorphic to a sphere, and that its face numbers minimize the expression $\max_{|x|\leq 1} |\sum_{j=0}^n (f_{j-1}/f_{n-1})\cdot 2^{-j}\cdot (x-1)^j|$ among the $f$-vectors of all $(n-1)$-dimensional simplicial complexes. The duals of the posets constructed have a recursive structure similar to face lattices of simplices or cubes, offering the study of a new special class of Eulerian partially ordered sets to test the validity of Stanleys conjecture on the non-negativity of the $cd$-index of all Gorenstein$^*$ posets.     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.     

Non-Unit Free Triangle Orders

A Free Triangle order is a partially ordered set in which every element can be represented by a triangle. All triangles lie between two parallel baselines, with each triangle intersecting each baseline in exactly one point. Two elements in the partially ordered set are incomparable if and only if their corresponding triangles intersect. A unit free triangle order is one with such a representation in which all triangles have the same area. In this paper, we present an example of a non-unit free triangle order.     

Dimension two,fixed points and dismantlable ordered sets

When does the fixed point property of a finite ordered set imply its dismantlability by irreducible elements? For instance, if it has width two. Although every finite ordered set is dismantlable by retractible (not necessarily irreducible) elements, surprisingly, a finite, dimension two ordered set, need not be dismantlable by irreducible elements. If, however, a finite ordered set with the fixed point property is N-free and of dimension two, then it is dismantlable by irreducibles. A curious consequence is that every finite, dimension two ordered set has a complete endomorphism spectrum.     

保持序和等价关系的自然偏序变换半群

设X为一个集合,■_X为X上的全变换半群.设E是X上的一个等价关系,定义T_E(X)={f∈■_X:■(x,y)∈E,(f(x),f(y))∈E},则T_E(X)是由等价关系E所确定的■_X的子半群.本文中,所考虑的集合X是一个有限全序集,同时E是非平凡的且所有的E-类都是凸集.显然■_E(X)={f∈T_E(X):■_x,y∈X,x≤y蕴涵f(x)≤f(y)}是T_E(X)的一个子半群.我们赋予■_E(X)自然偏序并讨论何时■_E(X)中的两个元素是关于这个偏序是相关的,然后确定■_E(X)中那些关于≤是相容的元素.此外,还描述了极大(极小)元和覆盖元.     

Automorphism group and dimension of ordered sets

It is shown that a finite groupG is isomorphic to the automorphism group of a two-dimensional ordered set if and only if it is a generalized wreath product of symmetric groups over an ordered index set that is a dual tree. Furthermore, every finite abelian group is isomorphic to the full automorphism group of a three-dimensional ordered set. Also every finite group is isomorphic to the automorphism group of an ordered set that does not contain an induced crown with more than four elements.     

The Fixed Point Property for Ordered Sets of Interval Dimension 2

We provide a polynomial time algorithm that identifies if a given finite ordered set is in the class of d2-collapsible ordered sets. For a d2-collapsible ordered set, the algorithm also determines if the ordered set is connectedly collapsible. Because finite ordered sets of interval dimension 2 are d2-collapsible, in particular, the algorithm determines in polynomial time if a given finite ordered set of interval dimension 2 has the fixed point property. This result is also a first step in investigating the complexity status of the question whether a given collapsible ordered set has the fixed point property.     

The Lattice of Completions of an Ordered Set

For any ordered set P, the join dense completions of P form a complete lattice K(P) with least element O(P), the lattice of order ideals of P, and greatest element M(P), the Dedekind–MacNeille completion P. The lattice K(P) is isomorphic to an ideal of the lattice of all closure operators on the lattice O(P). Thus it inherits some local structural properties which hold in the lattice of closure operators on any complete lattice. In particular, if K(P) is finite, then it is an upper semimodular lattice and an upper bounded homomorphic image of a free lattice, and hence meet semidistributive.