任务管理器打不开了-集中

2012有限集合上的组合数学问题

知识点：

1.偏序集合基本概念

一个集合
A
是所谓偏序的，是指它上面定 义了一个二元关系“

”满足下列条件：
1．若
xy
且
yx
同时成立，则
xy
（反对称律）
2．若
xy,yz
，则
xz
（传递律）
3．对于
A
的每一个
x
，都有
xx
（反身律）
4.
xyxy,xy.


特别地，如果每一对元素之间存在关系

，则称其为一个全序集合。

这里，符号

读作“小于等于”。

假定
(A,)是一个有限的偏序集合。由
A
中两两不可比较的元素所组成的子集合称为“不可比集合”（ 或
象一些学者所讲的，“反链”）；包含元素最多的不可比集合称为“最大不可比集合”（或极大“反链 ”）。用
M
表示一个最大不可比集合中元素的个数。

2.偏序集合基本问题和定理。

定理1（Dilworth 定理）.在将偏序集 合
A
分解成不相交链（相交亦可）的并时，所需要的链的最少个数
m
等于A
的最大不可比集中所含元素的个数。

注意：（1）这是组合数学理论中的又 一个“最大=最小”的定理，用它可以轻易地推出例7-15中的结论。
与Menger定理，“最大流 -最小割定理”和二部图中的“K
o
nig定理”遥相呼应。其实，这些“最大=最小”
型的结论之间存在者一定的蕴涵或等价关系。
（2）由于这个结果是如此重要，我们有必要再给出一 个快捷的证明（注意：快捷而简单的证明不一定是
“好”的证明！因为它的过于简单的过程会掩盖一些事 务的本质。没有经验的研究人员往往忽视这一点。）
下面这个证明来自于rg在1967年的篇文章。

证明2：设
P
是一个有限偏序集合。
P
中划分为不相交的 链的最小个数
m
=
P
中的一个反链所含元素的最
大个数。

显然有
mM
。对于
|P|
实行数学归纳。当
|P|
=0时定理显然成立。令
C
是一个极大链。如果
PC
的
每一个反 链至多包含
M1
个元素，则定理成立。因此，设
{a
1
,a
2
,...,a
M
}
为
PC
的一个反链。我们定
义：
''
S

{xP|i,xa
i
}.
类似第可以定义
S
。因为
C
的及大性，所以
C
中的最大 元素不再
S
里面。故，按照归纳假定，
S
是
M



个不相交的链
S
1

,S
2
的并，其中
a
i
S
i

.
假定
xS< br>i

,a
i

x,xa,
因为存在
j,< br>使得
xa
j
,
从而
,...,S
M
有a
i
a
j
,
与
{a
1
,a
2
,...,a
M
}
的定义相背！这就证明了
a
i
是
S
i

的极大元素
(i1,2,...,M)
。同理可 以对
S
i

进行证明，然后将链对接起来，就完成了定理的证明。

Mirsky与1971年给出了Dilworth定理的对偶定理：

定理2.设
P
是一个偏序集合，如果
P
不具有
m1
个元素的链，则< br>P
是
m
个反链的并。

证明：对于
m1,
定理显然成立。令
m2
且假定定理对于
m1
成立。令
P
是一个偏序集合没有长为
m1
的链。令
M
是
P
的极大元 素的集合，则
M
为一个反链。假定
x
1
x
2
. ..x
m
是
PM
的一条链，
那么它也是
P
的极 大链（因为
P
不具有
m1
个元素的链）。因此，
x
mM,
矛盾！因此，
PM
中没有
长为
m
的链。按照归 纳假设，
PM
是
m1
个反链的并。定理得证。

应用(用Dilworth定理证明Hall定理)
1,2,...m,}
和
k
个集合设集合系统
M
(S
1
,S
2
,... S,
m
)
满足条件：对于任意的自然数
k{
S
i
1
,S
i
2
,...S,
i
k
,


S
j1
k
i
j
S
i
1
 S
i
2
...S
i
k
k.
（*）
则，
M
(S
1
,S
2
,...,Sm
)
一定有SDR.
证明：令
T

S
i 1
m
i
为所有
S
集合中全体元素的并集合。我们可以定义一个偏序 关系如下：对于
S
i
和
t
i
T
，
S< br>i
t
i
t
i
S
i
。易见：|T|m.
假定最大反链有有
s
个元素，设其为
{S
1
,S
2
,...,S
k
,t
1
,t
2
,... ,t
l
},kls.
注意到
S
1
 S
2
...S
k
T{t
1
,t
2
,...,t
l
}
，
从（*）可知：
k|T|ls|T|
。这个偏序集合是
s
个不交的链的并，每一个最大反链中的元素位于
一个链上 。如果设
C
1
,C
2
,...,C
k
,C
k1
，...,C
kl
是这些不交链，且
C
i
(S
i
,a
i
)(i1,2,..,k),C
kj
(S< br>kj
,t
j
)(j1,2,...,l),

则
sm
（否则
S
1
,S
2
,....,S
kl< br>,...,S
m
是更大的反链）。这样，
(a
1
,...,a
k
,t
1
,...,t
l
)
为一个SDR.

教练员点评：我们可以反过来，利用Hall定理证明Dilworth定理 （读者不妨自己证明一下）。

3．Sperner定理

在集合论中有 一个基本问题已知为大家所关注，这就是所谓的相交集合问题：给定某个集合
S
的一簇子
集合
A
1
,A
2
,...,A
m
，它们之间两两 相交不空，
m
的最大可能值是多少?这个问题就是所谓的极值集合理论
中的最大相交子 集问题。在这一方面，最为著名的结果就是下面的Sperner定理。
定理3（Sperner定理 ）。如果
A
1
,A
2
,...,A
m
是
[ n]{1,2,...,n}
的一些子集合，满足条件：任意

n2
那么
mC
n
ijA
i
不是A
j
的子集。
.
。
教练员点评：所谓Sperner定理，就是计算偏序集合
(2
[n]
,|)
中最大反链的长度。

下面我们再来介绍一个典型的方法，在证明Sperner定理时使用过：

定理4（Erdos-Ko-Rado定理（1961））. 令
M
{A
1
,A
2
,...,A
m
}
是集合
[n]
的
m
个不同的
k
子集集合，
k1
使得任何两个子集之间有 非空的交，
kn2.
证明：
mC
n1.

证明:将1 到n这n个数由小到大排成一个圆圈。令
F
i
{i,i1,...,ik1} (modn)
（即，每一个数用n
除后所得余数的全体）。记
F{F
1,F
2
,...,F
n
}
为圈上所有
k
个相继 元素集合的全体。由于如果某个
F
i
等于
某个
A
j
，那么集合
{l,l1,...,lk1}
和
{lk,lk1,..., l1}(ilk)
中最多有一个在
M
中（否
则，有两个子集的交为空） ，所以
|MF|k.
对于
对于
F
上述结论仍然成立。因此有 < br>
{1,2,...,n}
应用一个置换

,
则由
F
得到
F

，那么




|M F

|kn!

S
n
我们固定
A
j
M(有m个),
和
F
i
F
（有
n个
） ，计算这个和，并且注意到使得
F
i
A
j
的置换有
k!(nk)!
个。因此

mnk!(nk)!mC


k1
n1

注意：在证明
|MF|k
的过程中，我们利用到了置换的这样一个性质：
设

是集合
X
上的一个置换，
A,BX,AB


(A)

(B)

.
< /p>

结论1.如果
|MF|k1
，则
F
中有两集合< br>F
i
,F
j
不相交，从而

(F
i
),

(F
j
)
也不交。
结论2.如果
|MF

|k1
，则
F
中有两集合
F
i
,F
j
不相交，从而

(F
i
),

(Fj
)
也不交。


练习题目

1.在ab1
只老鼠中，或者有一列老鼠有
a1
只，每一只都是前面一只的后代；或 者有
b1
只，其中没
有一只是另外一只的后代。

2.设
a
1
,a
2
,...,a
n
2
1
是整 数
1,2,...,n
2
1
的一个置换。证明：这个序列中一定有长度为< br>n1
的单调子序列。

3.设
Np
1
p
2
...p
n
是自然数
N
的质因数分解。则
N
的 两两无整除关系的因数的最大个数是
C
n
nnn
n2

。
4.设有自然数

235
。计算

的所有这样正因数的集 合的最大规模:这些正因数之间两两之间无整除
关系。

5.
Np
1
1
p
2
2
...p
n
n
是
N
的质因数分解。问
N
的一组两两无整除关系的因数的最大规模是多少？
6. 设
[n]{1,2,...,n].
如果我们定义
[n]
上的一个二元关系 “

”为
“
A,B2
[n]
[n]的幂集，ABAB
”
容易知道，
(2
[n]
,|)
形成一个偏序集合，而
2
[ n]
ee
e
中一个关系链
A
1
A
2
....A
m

形成一个 （关系）链，每一个
A
i
都在这个链中。如果上述链中所有元素都不相同，且没有更大 的链包含它，
则称其为一个极大链。设
A[n],|A|k.
试计算
2< br>
7.令
M
{A
1
,A
2
,...,A< br>m
}
是集合
[n]
的
m
个不同的子集的集合，使得对 于
m1
ijA
i
A
j
,A
i
A
j


,|A
i
|kn2,
则
mC
n1
。
[n]
中包含
A
的极大链的数目。
8 .设
x
1
,x
2
,...,x
n
是n个大于1的正 数。对于
A[n]
，记
x
A


间
I< br>，总共有
2
个和式
x
A
中属于
I
的至多有< br>C
n
n

x
iA
i
。则对于任何一个给定 长度为1的区
n2

个。