跳转到内容

极值组合学

维基百科,自由的百科全书

极值组合数学组合数学的一个领域,它本身就是数学的一部分。极值组合数学研究有限对象(数字图形向量集合等)的集合在满足某些限制的情况下可以有多大或多小。

极值组合数学大部分都与集合有关;这就是所谓的极值集合论。例如,在一个n元素集合的子集中,可以成对相交的k元素子集的最大数量是多少?最多能选取有多少个没有包含关系的子集?后一个问题由Sperner 定理回答,最大数量为,该定理推动了极值集合论的发展。

另一种例子:一个聚会,每三个人中有两个认识,两个不认识,可以邀请多少人?拉姆齐理论表明,最多有五个人可以参加这样的聚会。或者,假设给定一个有限的非零整数集,尽可能多地标记一些整数,并满足任意两个整数的和不能被标记。看起来(不论给什么整数)我们总是可以标记至少其中的三分之一。

另见

[编辑]
  • 极值图论
  • 绍尔-谢拉引理
  • Erdős–Ko–Rado 定理
  • 克鲁斯卡尔-卡托纳定理
  • 费舍尔不等式
  • 联合闭集猜想

参考

[编辑]