A Bipartite Analogue of Dilworth’s Theorem

Let m(n) be the maximum integer such that every partially ordered set P with n elements contains two disjoint subsets A and B, each with cardinality m(n), such that either every element of A is greater than every element of B or every element of A is incomparable with every element of B. We prove that . Moreover, for fixed ε ∈ (0,1) and n sufficiently large, we construct a partially ordered set P with n elements such that no element of P is comparable with other elements of P and for every two disjoint subsets A and B of P each with cardinality at least , there is an element of A that is comparable with an element of B.     

Partitioning -large sets: Some lower bounds

Let denote the property: if is an -large set of natural numbers and is partitioned into parts, then there exists a -large subset of which is homogeneous for this partition. Here the notion of largeness is in the sense of the so-called Hardy hierarchy. We give a lower bound for in terms of for some specific .

     

Reverse mathematics of separably closed sets

This paper contains a corrected proof that the statement “every non-empty closed subset of a compact complete separable metric space is separably closed” implies the arithmetical comprehension axiom of reverse mathematics.     

Algorithms for some graph theoretical optimization problems

This is a summary of the main results presented in the author’s PhD thesis. This thesis, written in English, was supervised by Frits Spieksma and defended on September 23, 2005 at the Katholieke Universiteit Leuven. A copy of the thesis is available from the authors website (http://www.econ. kuleuven.be/linda.moonen/public/). The thesis can be roughly split into two parts. The first part is dedicated to the problem of partitioning partially ordered sets into chains of limited size. The second part deals with the structure and the connectivity of the Internet.     

A poset hierarchy

This article extends a paper of Abraham and Bonnet which generalised the famous Hausdorff characterisation of the class of scattered linear orders. They gave an inductively defined hierarchy that characterised the class of scattered posets which do not have infinite incomparability antichains (i.e. have the FAC). We define a larger inductive hierarchy ^κℌ* which characterises the closure of the class of all κ-well-founded linear orders under inversions, lexicographic sums and FAC weakenings. This includes a broader class of “scattered” posets that we call κ-scattered. These posets cannot embed any order such that for every two subsets of size < κ, one being strictly less than the other, there is an element in between. If a linear order has this property and has size κ it is unique and called ℚ(κ). Partial orders such that for every a < b the set {x: a < x < b} has size ≥ κ are called weakly κ-dense, and posets that do not have a weakly κ-dense subset are called strongly κ-scattered. We prove that ^κℌ* includes all strongly κ-scattered FAC posets and is included in the class of all FAC κ-scattered posets. For κ = ℵ₀ the notions of scattered and strongly scattered coincide and our hierarchy is exactly aug(ℌ) from the Abraham-Bonnet theorem. The authors warmly thank Uri Abraham for his many useful suggestions and comments. Mirna Džamonja thanks EPSRC for their support on an EPSRC Advanced Fellowship.     

平面凸体的完全不等式组

对于平面凸体，分别用A、p、r、R、d表示它的面积、周长、内径、外径、直径．本文分别给出了其中的三元组合(A，r，R)，(p，r．R)，(p，r，d)，(A，r，d)所满足的不等式，并给出了相应的极值集．     

关于小伸缩商拟共形群的几个定理

本文研究了单位球Bn上小伸缩商拟共形群的离散性质，给出了一个收敛定理，并且证明了在一定限制条件下任意一个非初等非离散小伸缩商拟共形群含有一个二元生成的非初等非离散子群。     

Kautz网络中的最小反馈点集

对简单有向图D=(V，E)，顶点子集F∈V，如果由V＼F导出的子图不含有向圈，则称F是D的反馈点集。点数最小的子集F称为最小反馈点集。最小的点数称为反馈数。本利用Kautz最小轨道的方法确定出了Kautz有向图K(d，k)反馈数的一个下界和上界。并且具体给出了当k≤3时的反馈数。     

Stable cores of large games

We give general conditions, based on the largeness of the core, under which cores of exact TU games are their unique von Neumann-Morgenstern stable sets. We show that this condition is satisfied by convex games and by nonatomic exact market games. In this way, we extend and unify earlier results existing in literature. Under some additional conditions we also prove the equivalence between the core and the Mas-Colell bargaining set.We thank Jean-Francois Mertens, Enrico Minelli, William Thomson, and two anonymous referees for helpful comments. We also thank seminar audiences at CORE, Cornell, Pescara, and Rochester. We gratefully acknowledge the financial support of the Ministero dell’Istruzione, dell’Universitá e della Ricerca.     

直线Cantor集的Hausdorff中心测度

设K是由直线上迭代函数系统{φ1,φ2,…,φm}生成的吸引子,其中φi(z)=ρix+bi,i=1,2,…,m.称K为直线Cantor集.在压缩参数满足一定条件时,本文得到了K的Hausdorff中心测度精确值的计算公式.