"极大的无k个子集两两不相交的子集系的最小容量 (1987年)" 这篇论文探讨的是组合数学中的一个特定问题,涉及无k个子集两两不相交的子集系的容量。具体而言,它研究了一个有限集合S及其极大子集系~k(S),这个子集系满足以下两个条件: 1. 对于任何给定的k个子集A1, A2, ..., Ak,不存在两个子集A_i和A_j(i ≠ j)是互不相交的,即A_i ∩ A_j ≠ Ø。 2. 如果Ao是S的一个子集,且不属于~k(S),那么存在至少k-1个子集A1, ..., Ak-1在~k(S)中,使得它们与Ao两两不相交。 Erdös和Kleitman曾提出一个问题,即是否对于这样的子集系,其最小容量(即子集系中子集的总数)等于2^(n-1) - (n-k)? 这篇文章通过定理1和定理2给出了否定的回答,提供了关于~k(S)的更精确的下界。 定理1表明,对于一个极大的G3k子集系,其容量至少为2^n - 2^(n-k) + 1,这意味着存在这样一个子集系,其大小超过Erdös和Kleitman猜想的下界。 定理2进一步精确化了这个结果,指出存在一个极大的G3k子集系,其容量为2^n - 2^(n-k) + 1,这实际上是最小可能的容量。 为了证明这些定理,论文采用了一种构造性的方法,通过定义映射f将多(8\)X多(82)映射到多(8),并利用子集的投影P_i(A)来构建一个极大的G3k子集系。映射f允许作者在布尔代数的背景下考虑子集关系,从而证明了所提出的子集系满足所需的不相交性质。 论文的核心在于对子集系容量的理论分析,特别是对极大子集系容量的上下界的研究。这些问题在组合优化、图论以及信息理论等领域都有重要的应用,因为它们涉及到如何有效地组织和处理数据,以及在有限资源下如何达到最大的多样性。通过深入理解这些问题,可以为算法设计和数据结构提供理论支持,从而解决实际中的计算问题。
- 粉丝: 8
- 资源: 963
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆:CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析:财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合:快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计:自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南:解决兼容性与Office冲突
- MFC实现学生信息管理系统:登录与数据库操作