Dimension of the crown Skn

In 1941, Dushnik and Miller introduced the concept of the dimension of a poset (X, P) as the minimum number of linear extensions of P whose intersection is exactly P. Although Dilworth has given a formula for the dimension of distributive lattices, the general problem of determining the dimension of a poset is quite difficult. An equally difficult problem is to classify those posets which are dimension irreducible, i.e., those posets for which the removal of any point lowers the dimension. In this paper, we construct for each n≥3, k≥0, a poset, called a crown and denoted S^k_n, for which the dimension is given by the formula $\text{2?(n+k)}\text{(k+2)}$. Furthermore, for each t≥3, we show that there are infinitely many crowns which are irreducible and have dimension t. We then demonstrate a method of combining a collection of irreducible crowns to form an irreducible poset whose dimension is the sum of the crowns in the collection. Finally, we construct some infinite crowns possessing combinatorial properties similar to finite crowns.     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

Harmonics on posets

Given a finite ranked poset P, for each rank of P a space of complex valued functions on P called harmonics is defined. If the automorphism group G of P is sufficiently rich, these harmonic spaces yield irreducible representations of G. A decomposition theorem, which is analogous to the decomposition theorem for spherical harmonics, is stated. It is also shown that P can always be decomposed into posets whose principal harmonics are orthogonal polynomials. Classical examples are given.     

Posets admitting a unique order-compatible topology

A characterization is given for those posets (X, ?) such that X admits exactly one topology inducing the given partial order ?. As a corollary, a poset is finite if and only if it is finite-dimensional and admits a unique compatible topology. Related applications and examples are also developed.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

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.     

On the greedy dimension of a partial order

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.     

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.     

Maximal dimensional partially ordered sets III: a characterization of Hiraguchi's inequality for interval dimension

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?_n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?_n. Although |?₃|=24, for each n ≥ 4, ?_n contains only the crown S⁰_n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S⁰_n.     

Embedding finite posets in cubes

In this paper we define the n-cube Q_n as the poset obtained by taking the cartesian product of n chains each consisting of two points. For a finite poset X, we then define dim₂X as the smallest positive integer n such that X can be embedded as a subposet of Q_n. For any poset X we then have log₂ |X| ? dim₂X ? |X|. For the distributive lattice $\text{L =}\text{2}{}^{\mathrm{X}}$, dim₂L = |X| and for the crown S^k_n, dim₂ (S^k_n) = n + k. For each k ? 2, there exist positive constants c₁ and c₂ so that for the poset X consisting of all one element and k-element subsets of an n-element set, the inequality c₁ log₂n < dim₂(X) < c₂ log₂n holds for all n with k < n. A poset is called Q-critical if dim₂ (X ? x) < dim₂(X) for every x ? X. We define a join operation ⊕ on posets under which the collection Q of all Q-critical posets which are not chains forms a semigroup in which unique factorization holds. We then completely determine the subcollection $\text{M}$ ? Q consisting of all posets X for which dim₂ (X) = |X|.     

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.     

Classification of the factorial functions of Eulerian binomial and Sheffer posets

We give a complete classification of the factorial functions of Eulerian binomial posets. The factorial function B(n) either coincides with n!, the factorial function of the infinite Boolean algebra, or ²n−1, the factorial function of the infinite butterfly poset. We also classify the factorial functions for Eulerian Sheffer posets. An Eulerian Sheffer poset with binomial factorial function B(n)=n! has Sheffer factorial function D(n) identical to that of the infinite Boolean algebra, the infinite Boolean algebra with two new coatoms inserted, or the infinite cubical poset. Moreover, we are able to classify the Sheffer factorial functions of Eulerian Sheffer posets with binomial factorial function B(n)=²n−1 as the doubling of an upside-down tree with ranks 1 and 2 modified. When we impose the further condition that a given Eulerian binomial or Eulerian Sheffer poset is a lattice, this forces the poset to be the infinite Boolean algebra BX or the infinite cubical lattice . We also include several poset constructions that have the same factorial functions as the infinite cubical poset, demonstrating that classifying Eulerian Sheffer posets is a difficult problem.     

On the order of prime ideals

A posetX is isomorphic to the poset of all prime ideals of a (distributive) lattice with zero and unit if, and only if,X is the projective limit of an inverse system of finite posets.     

Planar Posets,Dimension, Breadth and the Number of Minimal Elements

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t ≥ 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d ≥ 2, there is an integer f(d) so that if P is a planar poset with dim(P) ≥ f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) ≥ d + 2. Here, we show that lim _d→∞ f(d)/d ≥ 2.     

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.     

Rings of differential operators on curves

Let k be an algebraically closed field of characteristic 0 and let A be a finitely generated k-algebra that is a domain whose Gelfand-Kirillov dimension is in [2, 3). We show that if A has a nonzero locally nilpotent derivation then A has quadratic growth. In addition to this, we show that A either satisfies a polynomial identity or A is isomorphic to a subalgebra of D(X), the ring of differential operators on an irreducible smooth affine curve X, and A is birationally isomorphic to D(X).     

The Involutory Dimension of Involution Posets

The involutory dimension, if it exists, of an involution poset P:=(P,,) is the minimum cardinality of a family of linear extensions of , involutory with respect to , whose intersection is the ordering . We show that the involutory dimension of an involution poset exists iff any pair of isotropic elements are orthogonal. Some characterizations of the involutory dimension of such posets are given. We study prime order ideals in involution posets and use them to generate involutory linear extensions of the partial ordering on orthoposets. We prove several of the standard results in the theory of the order dimension of posets for the involutory dimension of involution posets. For example, we show that the involutory dimension of a finite orthoposet does not exceed the cardinality of an antichain of maximal cardinality. We illustrate the fact that the order dimension of an orthoposet may be different from the involutory dimension.     

Topology of Hom complexes and test graphs for bounding chromatic number

The Hom complex of homomorphisms between two graphs was originally introduced to provide topological lower bounds on the chromatic number. In this paper we introduce new methods for understanding the topology of Hom complexes, mostly in the context of Γ-actions on graphs and posets (for some group Γ). We view the Hom(T, ⊙) and Hom(⊙, G) complexes as functors from graphs to posets, and introduce a functor (⊙)¹ from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of Hom complexes in terms of spaces of equivariant poset maps and Γ-twisted products of spaces. When P:= F(X) is the face poset of a simplicial complex X, this provides a useful way to control the topology of Hom complexes. These constructions generalize those of the second author from [17] as well as the calculation of the homotopy groups of Hom complexes from [8].     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

Path-Connected Partially Ordered Sets

The graph of a partially ordered set (X, ?) has X as its set of vertices and (x,y) is an edge if and only if x covers y or y covers x. The poset is path-connected if its graph is connected. Two integer-valued metrics, distance and fence, are defined for path-connected posets. Together the values of these metrics determine a path-connected poset to within isomorphism and duality. The result holds for path-connected preordered sets where distance and fence are pseudometrics. The result fails for non-path-connected posets.