Enumeration by kernel positions

We introduce a class of two-player games on posets with a rank function, in which each move of the winning strategy is unique. This allows one to enumerate the kernel positions by rank. The main example is a simple game on words in which the number of kernel positions of rank n is a signed factorial multiple of the nth Bernoulli number of the second kind. Generalizations to the degenerate Bernoulli numbers and to negative integer substitutions into the Bernoulli polynomials are developed. Using an appropriate scoring system for each function with an appropriate Newton expansion we construct a game in which the expected gain of a player equals the definite integral of the function on the interval [0,1].     

Resolutions of letterplace ideals of posets

We investigate resolutions of letterplace ideals of posets. We develop topological results to compute their multigraded Betti numbers, and to give structural results on these Betti numbers. If the poset is a union of no more than c chains, we show that the Betti numbers may be computed from simplicial complexes of no more than c vertices. We also give a recursive procedure to compute the Betti diagrams when the Hasse diagram of P has tree structure.     

Prime, irreducible elements and coatoms in posets

In this paper, some properties of prime elements, pseudoprime elements, irreducible elements and coatoms in posets are investigated. We show that the four kinds of elements are equivalent to each other in finite Boolean posets. Furthermore, we demonstrate that every element of a finite Boolean poset can be represented by one kind of them. The example presented in this paper indicates that this result may not hold in every finite poset, but all the irreducible elements are proved to be contained in each order generating set. Finally, the multiplicative auxiliary relation on posets and the notion of arithmetic poset are introduced, and some properties about them are generalized to posets.     

On orbits of order ideals of minuscule posets

An action on order ideals of posets considered by Fon-Der-Flaass is analyzed in the case of posets arising from minuscule representations of complex simple Lie algebras. For these minuscule posets, it is shown that the Fon-Der-Flaass action exhibits the cyclic sieving phenomenon, as defined by Reiner, Stanton, and White. A uniform proof is given by investigation of a bijection due to Stembridge between order ideals of minuscule posets and fully commutative Weyl group elements. This bijection is proven to be equivariant with respect to a conjugate of the Fon-Der-Flaass action and an arbitrary Coxeter element. If P is a minuscule poset, it is shown that the Fon-Der-Flaass action on order ideals of the Cartesian product P×[2] also exhibits the cyclic sieving phenomenon, only the proof is by appeal to the classification of minuscule posets and is not uniform.     

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.     

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.     

Filter-linkedness and its effect on preservation of cardinal characteristics

We introduce the property “F-linked” of subsets of posets for a given free filter F on the natural numbers, and define the properties “μ-F-linked” and “θ-F-Knaster” for posets in a natural way. We show that θ-F-Knaster posets preserve strong types of unbounded families and of maximal almost disjoint families.Concerning iterations of such posets, we develop a general technique to construct θ-Fr-Knaster posets (where Fr is the Frechet ideal) via matrix iterations of <θ-ultrafilter-linked posets (restricted to some level of the matrix). This is applied to prove consistency results about Cichoń's diagram (without using large cardinals) and to prove the consistency of the fact that, for each Yorioka ideal, the four cardinal invariants associated with it are pairwise different.At the end, we show that three strongly compact cardinals are enough to force that Cichoń's diagram can be separated into 10 different values.     

On forbidden configurations for strong posets

The concept of strong elements in posets is introduced. Several properties of strong elements in different types of posets are studied. Strong posets are characterized in terms of forbidden structures. It is shown that many of the classical results of lattice theory can be extended to posets. In particular, we give several characterizations of strongness for upper semimodular (USM) posets of finite length. We characterize modular pairs in USM posets of finite length and we investigate the interrelationships between consistence, strongness, and the property of being balanced in USM posets of finite length. In contrast to the situation in upper semimodular lattices, we show that these three concepts do not coincide in USM posets.     

Posets on up to 16 Points

In this article we describe a very efficient method to construct pairwise non-isomorphic posets (equivalently, T ₀ topologies). We also give the results obtained by a computer program based on this algorithm, in particular the numbers of non-isomorphic posets on 15 and 16 points and the numbers of labelled posets and topologies on 17 and 18 points.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Order varieties generated by finite posets

In a 1981 paper, Duffus and Rival define an order variety as a class of posets that is closed under the formation of products and retracts. They also introduce the notion of an irreducible poset. In the present paper we define nonextendible colored posets and certain minimal nonextendible colored posets that we call zigzags. We characterize via nonextendible colored posets the order varieties generated by a set of posets. If the generating set contains only finite posets our characterization is via zigzags. By using these theorems we give a characterization of finite irreducible posets.As an application we show that two different finite irreducible posets generate two different order varieties. We also show that there is a poset which has two different representations by irreducible posets. We thereby settle two open problems listed in the Duffus and Rival paper.     

A topological duality for posets

In this paper, we present a topological duality for partially ordered sets. We use the duality to give a topological construction of the canonical extension of a poset, and we also topologically represent the quasi-monotone maps, that is, maps from a finite product of posets to a poset that are order-preserving or order-reversing in each coordinate.     

Dominance elimination procedures on finite alternative games

A general definition of dominance elimination procedures for finite games is given which includes the multistage game representation of sophisticated voting for binary procedures. There then follows a proof that the set of outcomes resulting from the successive application of any dominance elimination procedure to any game in which each player has strict preferences over the alternatives, and in which the alternative and strategy spaces are finite, contains the set of outcomes attained by applying a procedure previously defined byFarquharson [1969].     

Equality of P-Partition Generating Functions

To every labeled poset (P, ω), one can associate a quasisymmetric generating function for its (P, ω)-partitions. We ask: when do two labeled posets have the same generating function? Since the special case corresponding to skew Schur function equality is still open, a complete classification of equality among (P, ω) generating functions is likely too much to expect. Instead, we determine necessary conditions and separate sufficient conditions for two labeled posets to have equal generating functions. We conclude with a classification of all equalities for labeled posets with small numbers of linear extensions.     

Algebraic properties of classes of path ideals of posets

We consider path ideals associated to special classes of posets such as tree posets and cycles. We express their property of being sequentially Cohen–Macaulay in terms of the underlying poset. Moreover, monomial ideals, which arise in algebraic statistics from the Luce-decomposable model and the ascending model, can be viewed as path ideals of certain posets. We study invariants of these so-called Luce-decomposable monomial ideals and ascending ideals for diamond posets and products of chains. In particular, for these classes of posets, we explicitly compute their Krull dimension, their projective dimension, their Castelnuovo–Mumford regularity and their Betti numbers.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Finite posets and topological spaces in locally finite varieties

We prove that if a finite connected poset admits an order-preserving Taylor operation, then all of its homotopy groups are trivial. We use this to give new characterisations of locally finite varieties omitting type 1 in terms of the posets (or equivalently, finite topological spaces) in the variety. Similar variants of other omitting-type theorems are presented. We give several examples of posets that admit various types of Taylor operations; in particular, we exhibit a topological space which is not an H-space but is compatible with a set of non-trivial identities, answering a question of W. Taylor.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived September 18, 2002; accepted in final form March 19, 2003.     

Definability in Substructure Orderings,II: Finite Ordered Sets

Let \({{\uppercase {\mathcal{p}}}} \) be the ordered set of isomorphism types of finite ordered sets (posets), where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite poset P, the set \(\{p,p^{\partial}\}\) is definable, where p and \(p^{\partial}\) are the isomorphism types of P and its dual poset. We prove that the only non-identity automorphism of \({{\uppercase {\mathcal{p}}}}\) is the duality map. Then we apply these results to investigate definability in the closely related lattice of universal classes of posets. We prove that this lattice has only one non-identity automorphism, the duality map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each member K of either of these two definable subsets, \(\{K,K^{\partial}\}\) is a definable subset of the lattice. Next, making fuller use of the techniques developed to establish these results, we go on to show that every isomorphism-invariant relation between finite posets that is definable in a certain strongly enriched second-order language \(\textup{\emph L}_2\) is, after factoring by isomorphism, first-order definable up to duality in the ordered set \({{\uppercase {\mathcal{p}}}}\). The language \(\textup{\emph L}_2\) has different types of quantifiable variables that range, respectively, over finite posets, their elements and order-relation, and over arbitrary subsets of posets, functions between two posets, subsets of products of finitely many posets (heteregenous relations), and can make reference to order relations between elements, the application of a function to an element, and the membership of a tuple of elements in a relation.