Differential Posets have Strict Rank Growth: A Conjecture of Stanley

We establish strict growth for the rank function of an r-differential poset. We do so by exploiting the representation theoretic techniques developed by Reiner and the author (Order 26(3):197–228, 2009) for studying related Smith forms.     

Strict Betweennesses Induced by Posets as well as by Graphs

For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V ³ such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let B_s(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V ³ such that y is an internal vertex on an induced path in G between x and z. The ternary relations B_s(P){\cal B}_s(P) and B_s(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation B_s(P)=B_s(G){\cal B}_s(P)={\cal B}_s(G).     

分层有限偏序集的直积

A new concept Graded Finite Poset is proposed in this paper.Through discussing some basic properties of it,we come to that the direct product of graded finite posets is connected if and only if every graded finite poset is connected.The graded function of a graded finite poset is unique if and only if the graded finite poset is connected.     

Ramsey Properties of Finite Posets

An important problem in topological dynamics is the calculation of the universal minimal flow of a topological group. When the universal minimal flow is one point, we say that the group is extremely amenable. For the automorphism group of Fra?ssé structures, this problem has been translated into a question about the Ramsey and ordering properties of certain classes of finite structures by Kechris et al. (Geom Funct Anal 15:106–189, 2005). Using the Schmerl list (Schmerl, Algebra Univers 9:317–321, 1979) of Fra?ssé posets, we consider classes of finite posets with arbitrary linear orderings and linear orderings that are linear extensions of the partial ordering. We provide classification of each of these classes according to their Ramsey and ordering properties. Additionally, we extend the list of extremely amenable groups as well as the list of metrizable universal minimal flows.     

有限偏序集的Cartesian积的收缩

通过对有限偏序集的Cartesian积的收缩的考查,证明了Plotkin在1978年提出的一个猜想,并部分回答了Mislove和Lawson在"Open Problems in Topology"中提出的一个公开问题.     

Ramsey Properties of Finite Posets II

We classify Fra?ssé classes of finite posets with convex linear orderings with respect to the Ramsey property and extend the list of extremely amenable groups and universal minimal flows thanks to a theory developed by Kechris et al. (Geom Funct Anal 15:106–189, 2005). For the structures from the Schmerl list for which this technique is not applicable, we provide a direct calculation of universal minimal flows.     

Connectivity Properties of Factorization Posets in Generated Groups

Order - We consider three notions of connectivity and their interactions in partially ordered sets coming from reduced factorizations of an element in a generated group. While one form of...     

Incomparability and Intersection Properties of Boolean Interval Lattices and Chain Posets

In a canonical way, we establish an AZ-identity (see [2]) and its consequences, the LYM-inequality and the Sperner property, for the Boolean interval lattice. Furthermore, the Bollobas inequality for the Boolean interval lattice turns out to be just the LYM-inequality for the Boolean lattice. We also present an Intersection Theorem for this lattice.Perhaps more surprising is that by our approach the conjecture of P. L. Erdöset al.[7] and Z. Füredi concerning an Erdös–Ko–Rado-type intersection property for the poset of Boolean chains could also be established. In fact, we give two seemingly elegant proofs.     

On Posets of Page Number 2

In this paper we deal with the page number of partially ordered sets (posets). We provide a lower bound in the terms of the jump number and then study posets with page number 2.     

Order Dimension,Strong Bruhat Order and Lattice Properties for Posets

We determine the order dimension of the strong Bruhat order on finite Coxeter groups of types A, B and H. The order dimension is determined using a generalization of a theorem of Dilworth: dim (P)=width(Irr(P)), whenever P satisfies a simple order-theoretic condition called here the dissective property (or clivage). The result for dissective posets follows from an upper bound and lower bound on the dimension of any finite poset. The dissective property is related, via MacNeille completion, to the distributive property of lattices. We show a similar connection between quotients of the strong Bruhat order with respect to parabolic subgroups and lattice quotients.     

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.     

代数的局部完备集范畴和FS-局部dcpo范畴的笛卡儿闭性

本文引入了代数的局部完备集,FS-局部dcpo,局部稳定映射等概念．主要结果是：以局部Scott连续映射为态射的代数的局部完备集范畴,以局部稳定映射为态射的代数的局部完备集范畴以及以局部Scott连续映射为态射的FS-局部dcpo范畴都是笛卡儿闭范畴．     

Mpi-空间与偏序集

通过建立mpi-空间和偏序集之间的对应关系,在同构意义下,得到无环mpi-空间的特征.利用这种持征,mpi-空间的一些结果可以转化到偏序集框架结构下进行研究.这些成果清楚地表明这里所提供的思想是研究mpi-空间的一个新方法.最后,概述了我们未来的一些工作.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Strict 2-threshold graphs

A graph G is called a strict 2-threshold graph if its edge-set can be partitioned into two threshold graphs T₁ and T₂ such that every triangle of G is also a triangle of T₁ or of T₂. We indicate a polynomial-time algorithm to recognize these graphs and characterize them by forbidden configurations.     

Bier Spheres and Posets

In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n – 2)-spheres on 2n vertices, as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that “cut across an ideal.” Thus we arrive at a substantial generalization of Bier’s construction: the Bier posets Bier(P, I) of an arbitrary bounded poset P of finite length. In the case of face posets of PL spheres this yields cellular “generalized Bier spheres.” In the case of Eulerian or Cohen–Macaulay posets P we show that the Bier posets Bier(P, I) inherit these properties. In the boolean case originally considered by Bier, we show that all the spheres produced by his construction are shellable, which yields “many shellable spheres,” most of which lack convex realization. Finally, we present simple explicit formulas for the g-vectors of these simplicial spheres and verify that they satisfy a strong form of the g-conjecture for spheres.     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Topological degree and the Sperner lemma

In this paper, we give a new proof of Sperner's lemma, in its superstrong from, using the topological degree. Thus, we point out a relation between several methods for fixed-point theorems using either the topological degree, or the KKM lemma, or the Sperner lemma.The author would like to thank Dr. G. Leitmann for his remarks and suggestions.