当前位置:文档下载 > 所有分类 > On
侵权投诉

On

the cofinality of infinite partially ordered sets: factoring a poset into lean essential subsets

On the co?nality of in?nite partially ordered sets: factoring a poset into lean essential subsets

Reinhard Diestel Oleg Pikhurko

8February2003

Keywords:in?nite posets,co?nality,poset decomposition

MSC2000:06A0706A11

Abstract

We study which in?nite posets have simple co?nal subsets such as

chains,or decompose canonically into such subsets.The posets of

countable co?nality admitting such a decomposition are characterized

by a forbidden substructure;the corresponding problem for uncount-

able co?nality remains open.

1Introduction

A subset Q of a partially ordered set(P,≤)is co?nal in P if for every x∈P there exists a y∈Q with x≤y.The least cardinality of a co?nal subset of P is the co?nality cf(P)of P.

In this paper,we shall work from the assumption that we‘understand’an in?nite poset(P,≤)as soon as we understand one of its co?nal subsets, and our aim will be to either?nd in P a particularly simple co?nal subset Q (which may then be studied instead of P),or to decompose P into such simple subsets.This paradigm makes immediate sense,for example,if P is itself a down-closed subset of some larger poset,and‘understanding’P means being able to decide which elements of that larger poset it contains.1 1In the context[2]from which this study arose,P would be a property of?nite graphs, such as planarity with the graph minor relation.In this example,the grids form a co?nal subset of P(since every planar graph is a minor of some grid),and indeed for many minor-related questions it su?ces to consider grids instead of arbitrary planar graphs.

1

第1页

免费下载Word文档免费下载:On

(下载1-16页,共16页)

我要评论

TOP相关主题

返回顶部