Continuum limits for classical sequential growth models

A random graph order, also known as a transitive percolation process, is defined by taking a random graph on the vertex set {0,…,n ? 1} and putting i below j if there is a path i = i₁…i_k = j in the graph with i₁ < … < i_k. Rideout and Sorkin 14 provide computational evidence that suitably normalized sequences of random graph orders have a “continuum limit.” We confirm that this is the case and show that the continuum limit is always a semiorder. Transitive percolation processes are a special case of a more general class called classical sequential growth models. We give a number of results describing the large‐scale structure of a general classical sequential growth model. We show that for any sufficiently large n, and any classical sequential growth model, there is a semiorder S on {0,…,n ‐ 1} such that the random partial order on {0,…,n ‐ 1} generated according to the model differs from S on an arbitrarily small proportion of pairs. We also show that, if any sequence of classical sequential growth models has a continuum limit, then this limit is (essentially) a semiorder. We give some examples of continuum limits that can occur. Classical sequential growth models were introduced as the only models satisfying certain properties making them suitable as discrete models for spacetime. Our results indicate that this class of models does not contain any that are good approximations to Minkowski space in any dimension ≥ 2. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Principal Γ-cone for a tree

For any tree Γ, we introduce Γ-cones consisting of chambers and enumerate the number of chambers contained in two particular (called principal) Γ-cones. The problem is equivalent to the combinatorial problem of the enumeration of linear extensions of two bipartite orderings on a tree Γ. We characterize the principal Γ-cones among other Γ-cones by the strict maximality of the number of their chambers, and give a formula for this maximal (called principal) number by a finite sum of hook length formulae. We explain the formula through the simplicial block decomposition of principal Γ-cones. The results have their origin and application in the study of the topology related to Coxeter groups and Artin groups.     

On the core of ordered submodular cost games

A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed. Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000     

On Beck’s coloring of posets

We study Beck-like coloring of partially ordered sets (posets) with a least element 0. To any poset P with 0 we assign a graph (called a zero-divisor graph) whose vertices are labelled by the elements of P with two vertices x,y adjacent if 0 is the only element lying below x and y. We prove that for such graphs, the chromatic number and the clique number coincide. Also, we give a condition under which posets are not finitely colorable.     

Relations on generalized degree sequences

We study degree sequences for simplicial posets and polyhedral complexes, generalizing the well-studied graphical degree sequences. Here we extend the more common generalization of vertex-to-facet degree sequences by considering arbitrary face-to-flag degree sequences. In particular, these may be viewed as natural refinements of the flag f-vector of the poset. We investigate properties and relations of these generalized degree sequences, proving linear relations between flag degree sequences in terms of the composition of rank jumps of the flag. As a corollary, we recover an f-vector inequality on simplicial posets first shown by Stanley.     

Orthocomplemented Posets with a Symmetric Difference

We endow orthocomplemented posets with a binary operation–an abstract symmetric difference of sets–and we study algebraic properties of this class, . Denoting its elements by ODP, we first investigate on the features related to compatibility in ODPs. We find, among others, that any ODP is orthomodular. This explicitly links with the theory of quantum logics. By analogy with Boolean algebras, we then ask if (when) an ODP is set representable. Though we find that general ODPs do not have to be set representable, many natural ODPs are shown to be. We characterize the set-representable ODPs in terms of two valued morphisms and prove that they form a quasivariety. This quasivariety contains the class of pseudocomplemented ODPs as we show afterwards. At the end we ask whether any orthomodular poset can be converted or, more generally, enlarged to an ODP. By countre-examples we answer these questions to the negative. The authors acknowledge the support of the research plan MSM 0021620839 that is financed by the Ministry of Education of the Czech Republic and the grant GAČR 201/07/1051 of the Czech Grant Agency.     

Differential Posets and Smith Normal Forms

We conjecture a strong property for the up and down maps U and D in an r-differential poset: DU + tI and UD + tI have Smith normal forms over . In particular, this would determine the integral structure of the maps U, D, UD, DU, including their ranks in any characteristic. As evidence, we prove the conjecture for the Young-Fibonacci lattice Y F studied by Okada and its r-differential generalizations Z(r), as well as verifying many of its consequences for Young’s lattice Y and the r-differential Cartesian products Y ^r .     

基于有限辛空间的一致偏序集和Leonard对

设F_q为q个元素的有限域,q是一个素数的幂.令F_q~((2v))是F_q上的2v维辛空间,M(m,s;2v)表示辛群作用在F_q~((2v))上的子空间的轨道.L(m,s;2v)是M(m,s;2v)的子空间生成的集合.若按照子空间的包含关系来规定L(m,s;2v)的序,则得一偏序集,记为L_O(m,s;2v).本文,首先构造了L(m,s;2v)上的子偏序集L_O(m,s;2v),然后证明这个子偏序集是强一致偏序的.最后利用这个偏序集构造了Leonard对.     

蕴含权重的偏序集多准则决策法

针对偏序集方法不能解决含有权重的多准则决策问题,提出一种“隐式”赋权的偏序决策方法。首先将含有m个方案和n个准则的决策问题表示成偏序集,之后按权重由大到小的顺序,对准则进行逐步相加形成n个新的准则,得到一个新的偏序集。根据偏序集间的包含关系,证明了新偏序集不仅蕴含了权重信息,而且比初始偏序集有更强的排序能力。结果表明,该法在应用中仅需获取权重排序信息,无需精确权重,适用于权重难以确定的多准则决策问题。以三峡库区水质评价为例,例子表明新方法明显优于原有的偏序决策方法,能够对13个方案进行聚类和排序,而原有方法在该例中几乎难以应用。     

A specialization of prinjective Ringel-Hall algebra and the associated Lie algebra

In the present paper we describe a specialization of prinjective Ringel-Hall algebra to 1, for prinjective modules over incidence algebras of posets of finite prinjective type, by generators and relations. This gives us a generalisation of Serre relations for semisimple Lie algebras. Connections of prinjective Ringel-Hall algebras with classical Lie algebras are also discussed.