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.     

自由正交模格FMOk(n)的自同构群

文章先利用自同构映射保有限并的性质研究了一般正交模格的次直积的自同构群与自同构群的次直积的关系,再用块置换的方法研究了MOk的自同构群的生成元集,由此得到自由正交模格FMOk(n)的自同构群的直积分解式,从而完全解决了FMOk(n)的自同构群的结构问题.     

带Morita对偶的偏序集环

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

一个绘制统筹图的算法

统筹图又叫计划网络图。任给一个其元素叫做工序（或作业或活动）的有限偏序集，要绘制它的一个最优统筹图，限含虚工序数目为最少者，是一个尚未从理论上解决的问题。本文讨论了虚工序产生的原因和如何减少虚工序数量的一些途径；指出了高度为二的编序集其最优统筹图含虚工序数目达到最大且等于该偏序集框图的边数的充分必要条件；本文给出了一个绘制最优统筹图的近似算法，此算法弥补了文[2]和[3]所给算法的一些不足之处。     

T0-spaces and pointwise convergence

The purpose of this paper is to give several different characterizations of those T₀-spaces E with the property that if F:X × E → Y is separately continuous, then it is jointly continuous. One such is that the lattice 0(E) of open sets of E be a hypercontinuous lattice (i.e. the interval topology on 0(E) is Hausdorff). If E is a sober space, then E must be a quasicontinuous poset endowed with the Scott topology.     

On Uniquely Complemented Posets

In this paper, some classical results of uniquely complemented lattices are extended to uniquely complemented posets (with 0 and 1) like Peirce's Theorem, the Birkhoff–von Neumann Theorem, the Birkhoff–Ward Theorem. Further, it is shown that a section semi-complemented pseudocomplemented poset is a Boolean poset. Mathematics Subject Classification (2001) 06A06, 06A11, 06C15, 06C20, 06D15     

Properties of four partial orders on standard Young tableaux

Let SYTn be the set of all standard Young tableaux with n cells. After recalling the definitions of four partial orders, the weak, KL, geometric and chain orders on SYTn and some of their crucial properties, we prove three main results:

•

Intervals in any of these four orders essentially describe the product in a Hopf algebra of tableaux defined by Poirier and Reutenauer.

•

The map sending a tableau to its descent set induces a homotopy equivalence of the proper parts of all of these orders on tableaux with that of the Boolean algebra ²[n−1]. In particular, the Möbius function of these orders on tableaux is (−1)ⁿ⁻³.

•

For two of the four orders, one can define a more general order on skew tableaux having fixed inner boundary, and similarly analyze their homotopy type and Möbius function.

     

The Gold Partition Conjecture

We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample.