q-Weighted log-concavity and q-product theorem on the normality of posets

We show that q-weighted log-concavity and the strict normalized matching property are preserved under the q-direct product over weighted posets. As consequences, two classes of weighted posets including the finite linear lattices are strictly q-weighted log-concave and strictly normal.     

测度拓扑和连续偏序集的刻画

研究偏序集上的测度拓扑以及与其它内蕴拓扑间的关系,利用测度拓扑刻画了偏序集的连续性.构造了反例说明存在完全分配格,其上的测度拓扑不是连续格从而不是局部紧拓扑.     

带Morita对偶的偏序集环

设Ｒ是有１的结合环，Ｉ是任意偏序集，ＲＩ是Ｒ上Ｉ的偏序集环．本文考虑了带对偶的偏序集环，得到：ＲＩ带Ｍｏｒｉｔａ对偶当且仅当Ｒ带Ｍｏｒｉｔａ对偶．推广了已有的在Ｒ是有限偏序集时的有关结果     

Loopless Generation of Linear Extensions of a Poset

Canfield and Williamson gave the first loopless algorithm for generating all linear extensions of a poset. It elegantly generates all signed extensions, resulting in each extension appearing somewhere with each sign, but retains only every other one independent of its sign. It uses an array for the extension. In this paper we give another loopless algorithm for generating all the linear extensions. It generates each extension only once and uses a list for the extensions.     

Weak Factorization Systems and Topological Functors

Weak factorization systems, important in homotopy theory, are related to injective objects in comma-categories. Our main result is that full functors and topological functors form a weak factorization system in the category of small categories, and that this is not cofibrantly generated. We also present a weak factorization system on the category of posets which is not cofibrantly generated. No such weak factorization systems were known until recently. This answers an open problem posed by M. Hovey.     

Dominant regions in noncrystallographic hyperplane arrangements

For a crystallographic root system, dominant regions in the Catalan hyperplane arrangement are in bijection with antichains in a partial order on the positive roots. For a noncrystallographic root system, the analogous arrangement and regions have importance in the representation theory of an associated graded Hecke algebra. Since there is also an analogous root order, it is natural to hope that a similar bijection can be used to understand these regions. We show that such a bijection does hold for type H₃ and for type I₂(m), including arbitrary ratio of root lengths when m is even, but does not hold for type H₄. We give a criterion that explains this failure and a list of the 16 antichains in the H₄ root order which correspond to empty regions.     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

The Möbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [σ,π] in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2,…,k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142.We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [σ,π] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of (1,π) is either 0, 1 or −1.     

(Un)stable matchings with blocking costs

We introduce and study weighted bipartite matching problems under strict preferences where blocking edges can be paid for, thus imposing costs rather than constraints as in classical models. We focus on the setting in which the weight of an edge represents the benefit from including it in the matching and/or the cost if it is a blocking edge. We show that this setting encompasses interesting special cases that remain polynomially-solvable, although it becomes APX-hard even in a quite restricted case.