主题
Search

并闭集猜想


A={A_1,A_2,...,A_n} 为一个 并闭集,则并闭集猜想指出,存在一个元素,它至少属于 n/2A 中的集合。Sarvate 和 Renaud (1989) 表明,如果 |A_1|<=2,其中 A_1A 中最小的集合,或者如果 n<11,则该猜想成立。他们还表明,如果该猜想不成立,则 |A_1|<|A_n|/2,其中 A_nA 中最大的集合。

此后,对于 n 最大到 18 (Sarvate 和 Renaud 1990)、24 (Lo Faro 1994a)、27 (Poonen 1992)、32 (Gao 和 Yu 1998) 以及已知的最佳结果 40 (Roberts 1992),这些结果得到了改进。

对于 A 具有 2-元素集合的情况,证明可以如下进行。令 A_1={x,y},然后根据集合与 A_1 的交集是 emptyset{x}{y} 还是 {x,y},将 A 的集合划分为四个不相交的族 B_0B_xB_yB_(xy)。由此得出 |B_(xy)|>=|B_0|,通过与 A_1 取并集得到,其中 |B|基数 B。现在比较 |B_x||B_y|。如果 |B_x|>=|B_y|,则 |B_x|+|B_xy|>=|B_0|+|B_y|,因此 x 至少在 A 的一半集合中。类似地,如果 |B_x|<=|B_y|,则 y 至少在一半的集合中(Hoey,私人通讯)。

遗憾的是,这种证明方法不能扩展到 |A_1|=3,因为 Sarvate 和 Renaud 展示了一个 并闭集 的例子,其中 A_1={x,y,z}xyz 都不在集合的一半中。然而,在这些情况下,存在其他元素确实出现在集合的一半中,因此这不是对该猜想的反例,而只是对上述证明方法的限制(Hoey,私人通讯)。


另请参阅

并闭集

使用 Wolfram|Alpha 探索

参考文献

Gao, W. 和 Yu, H. "关于并闭集猜想的注记。" Ars Combin. 49, 280-288, 1998.Lo Faro, G. "关于并闭集猜想的注记。" J. Austral. Math. Soc. Ser. A 57, 230-236, 1994a.Lo Faro, G. "并闭集猜想:改进的界限。" J. Combin. Math. Combin. Comput. 16, 97-102, 1994b.Poonen, B. "并闭族。" J. Combin. Theory Ser. A 59, 253-268, 1992.Roberts, I. 技术报告 No. 2/92. School Math. Stat., Curtin Univ. Tech., Perth, 1992.Sarvate, D. G. 和 Renaud, J.-C. "关于并闭集猜想。" Ars Combin. 27, 149-153, 1989.Sarvate, D. G. 和 Renaud, J.-C. "并闭集猜想的改进界限。" Ars Combin. 29, 181-185, 1990.West, D. "并闭集猜想 (1979)." http://www.math.uiuc.edu/~west/openp/unionclos.html.

在 Wolfram|Alpha 中引用

并闭集猜想

请这样引用

Weisstein, Eric W. "并闭集猜想。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Union-ClosedSetsConjecture.html

主题分类