Finite Eulerian posets which are binomial, Sheffer or triangular

In this paper we study finite Eulerian posets which are binomial, Sheffer or triangular. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows:

•

We completely determine the structure of Eulerian binomial posets and, as a conclusion, we are able to classify factorial functions of Eulerian binomial posets.

•

We give an almost complete classification of factorial functions of Eulerian Sheffer posets by dividing the original question into several cases.

•

In most cases above, we completely determine the structure of Eulerian Sheffer posets, a result stronger than just classifying factorial functions of these Eulerian Sheffer posets.

We also study Eulerian triangular posets. This paper answers questions posed by R. Ehrenborg and M. Readdy. This research is also motivated by the work of R. Stanley about recognizing the boolean lattice by looking at smaller intervals.     

Level Eulerian Posets

The notion of level posets is introduced. This class of infinite posets has the property that between every two adjacent ranks the same bipartite graph occurs. When the adjacency matrix is indecomposable, we determine the length of the longest interval one needs to check to verify Eulerianness. Furthermore, we show that every level Eulerian poset associated to an indecomposable matrix has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem–Mahler–Lech theorem, the ab-series of a level poset is shown to be a rational generating function in the non-commutative variables a and b. In the case the poset is also Eulerian, the analogous result holds for the cd-series. Using coalgebraic techniques a method is developed to recognize the cd-series matrix of a level Eulerian poset.     

Coproducts and the cd-Index

The linear span of isomorphism classes of posets, P, has a Newtonian coalgebra structure. We observe that the ab-index is a Newtonian coalgebra map from the vector space P to the algebra of polynomials in the noncommutative variables a and b. This enables us to obtain explicit formulas showing how the cd-index of the face lattice of a convex polytope changes when taking the pyramid and the prism of the polytope and the corresponding operations on posets. As a corollary, we have new recursion formulas for the cd-index of the Boolean algebra and the cubical lattice. Moreover, these operations also have interpretations for certain classes of permutations, including simsun and signed simsun permutations. We prove an identity for the shelling components of the simplex. Lastly, we show how to compute the ab-index of the Cartesian product of two posets given the ab-indexes of each poset.     

On Poset Boolean Algebras

Let (P,≤) be a partially ordered set. The poset Boolean algebra of P, denoted F(P), is defined as follows: The set of generators of F(P) is {x _p  : p∈P}, and the set of relations is {x _p ⋅x _q =x _p  : p≤q}. We say that a Boolean algebra B is well-generated, if B has a sublattice G such that G generates B and (G,≤ ^B |G) is well-founded. A well-generated algebra is superatomic. THEOREM 1. Let (P,≤) be a partially ordered set. The following are equivalent. (i) P does not contain an infinite set of pairwise incomparable elements, and P does not contain a subset isomorphic to the chain of rational numbers, (ii) F(P) is superatomic, (iii) F(P) is well-generated. The equivalence (i) ⇔ (ii) is due to M. Pouzet. A partially ordered set W is well-ordered, if W does not contain a strictly decreasing infinite sequence, and W does not contain an infinite set of pairwise incomparable elements. THEOREM 2. Let F(P) be a superatomic poset algebra. Then there are a well-ordered set W and a subalgebra B of F(W), such that F(P) is a homomorphic image of B. This is similar but weaker than the fact that every interval algebra of a scattered chain is embeddable in an ordinal algebra. Remember that an interval algebra is a special case of a poset algebra. This revised version was published online in June 2006 with corrections to the Cover Date.     

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 zero divisor graphs of Boolean posets

In this paper, it is proved that if B is a Boolean poset and S is a bounded pseudocomplemented poset such that S\Z(S) = {1}, then Γ(B) ≌ Γ(S) if and only if B ≌ S. Further, we characterize the graphs which can be realized as zero divisor graphs of Boolean posets.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Peak quasisymmetric functions and Eulerian enumeration

Via duality of Hopf algebras, there is a direct association between peak quasisymmetric functions and enumeration of chains in Eulerian posets. We study this association explicitly, showing that the notion of cd-index, long studied in the context of convex polytopes and Eulerian posets, arises as the dual basis to a natural basis of peak quasisymmetric functions introduced by Stembridge. Thus Eulerian posets having a nonnegative cd-index (for example, face lattices of convex polytopes) correspond to peak quasisymmetric functions having a nonnegative representation in terms of this basis. We diagonalize the operator that associates the basis of descent sets for all quasisymmetric functions to that of peak sets for the algebra of peak functions, and study the g-polynomial for Eulerian posets as an algebra homomorphism.     

Depth of Boolean functions over an arbitrary infinite basis

Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer n as the minimal depth D _B (n) of the circuits sufficient to realize every Boolean function on n variables over a basis B. It is shown that, for each infinite basis B, either there exists a constant β ? 1 such that D _B (n) = β for all sufficiently large n or there exist an integer constant γ ? 2 and a constant δ such that log _γ n ? D _B (n) ? log _γ n + δ for all n.     

The Tchebyshev Transforms of the First and Second Kind

An in-depth study of the Tchebyshev transforms of the first and second kind of a poset is taken. The Tchebyshev transform of the first kind is shown to preserve desirable combinatorial properties, including EL-shellability and nonnegativity of the cd-index. When restricted to Eulerian posets, it corresponds to the Billera, Ehrenborg, and Readdy omega map of oriented matroids. The Tchebyshev transform of the second kind U is a Hopf algebra endomorphism on the space of quasisymmetric functions which, when restricted to Eulerian posets, coincides with Stembridge’s peak enumerator. The complete spectrum of U is determined, generalizing the work of Billera, Hsiao, and van Willigenburg. The type B quasisymmetric function of a poset is introduced and, like Ehrenborg’s classical quasisymmetric function of a poset, it is a comodule morphism with respect to the quasisymmetric functions QSym. Finally, similarities among the omega map, Ehrenborg’s r-signed Birkhoff transform, and the Tchebyshev transforms motivate a general study of chain maps which occur naturally in the setting of combinatorial Hopf algebras.     

The depth of Boolean functions realized by circuits over an arbitrary basis

Realization of Boolean functions by circuits of functional elements is considered over arbitrary complete bases (including infinite ones). The depth of a circuit means the maximal number of functional elements forming an oriented chain going from inputs of the circuit to its output. It is shown that for any basis B the growth order of the Shannon function of depth D _B (n) for n → ∞ is equal to 1, log₂ n, or n, and the latter case appears if and only if the basis B is finite.     

Peckness of Edge Posets

For any graded poset P, we define a new graded poset, ??(P), whose elements are the edges in the Hasse diagram of P. For any group G acting on the boolean algebra B _n in a rank-preserving fashion we conjecture that ??(B _n /G) is Peck. We prove that the conjecture holds for “common cover transitive” actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.     

Semigroup actions on posets and preimage quasi-orders

Structures consisting of a semigroup of (partial) functions on a set X, a?poset of subsets of X, and a preimage operation linking the two, arise commonly throughout mathematics. The poset may be equipped with one or more set operations, up to Boolean algebra structure. Such structures are finitely axiomatized here in terms of order-preserving semigroup actions on posets. This generalises Schein??s axiomatization of semigroups of partial functions equipped with the first projection quasi-order.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Notes on Free Monadic Boolean Algebras

If F B(2 ⁿ – 1) denotes the Boolean algebra with 2 ⁿ – 1 free generators and P(2 ⁿ ) is the Cartesian product of 2 ⁿ Boolean algebras all equal to F B(2 ⁿ – 1), we define on P(2 ⁿ ) an existential quantifier by means of a relatively complete Boolean subalgebra of P(2 ⁿ ) and we prove that (P(2ⁿ),) is the monadic Boolean algebra with n free generators. Every element of P(2 ⁿ ) is a 2 ⁿ -tuple whose coordinates are in F B(2 ⁿ – 1); in particular, so are the n generators of P(2 ⁿ ). We indicate in this work the coordinates of the n generators of P(2 ⁿ ).     

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.     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.     

On derived equivalences of categories of sheaves over finite posets

A finite poset X carries a natural structure of a topological space. Fix a field k, and denote by D^b(X) the bounded derived category of sheaves of finite dimensional k-vector spaces over X. Two posets X and Y are said to be derived equivalent if D^b(X) and D^b(Y) are equivalent as triangulated categories.We give explicit combinatorial properties of X which are invariant under derived equivalence; among them are the number of points, the Z-congruency class of the incidence matrix, and the Betti numbers. We also show that taking opposites and products preserves derived equivalence.For any closed subset Y⊆X, we construct a strongly exceptional collection in D^b(X) and use it to show an equivalence D^b(X)?D^b(A) for a finite dimensional algebra A (depending on Y). We give conditions on X and Y under which A becomes an incidence algebra of a poset.We deduce that a lexicographic sum of a collection of posets along a bipartite graph S is derived equivalent to the lexicographic sum of the same collection along the opposite .This construction produces many new derived equivalences of posets and generalizes other well-known ones.As a corollary we show that the derived equivalence class of an ordinal sum of two posets does not depend on the order of summands. We give an example that this is not true for three summands.     

A study on monotone self-dual Boolean functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).     

Boolean Lattices: Ramsey Properties and Embeddings

A subposet Q ^′ of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q ^′ such that x ≤ y in P iff f(x) ≤ f(y) in Q. For posets P, P ^′, let the poset Ramsey number R(P, P ^′) be the smallest N such that no matter how the elements of the Boolean lattice Q _N are colored red and blue, there is a copy of P with all red elements or a copy of P ^′ with all blue elements. We provide some general bounds on R(P, P ^′) and focus on the situation when P and P ^′ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q _n in Q _N and for a multicolor version of a poset Ramsey number.