主題
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,私人通訊)。


另請參閱

並閉集

使用 探索

參考文獻

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.

在 中引用

並閉集猜想

請這樣引用

Weisstein, Eric W. "並閉集猜想。" 來自 Web 資源。 https://mathworld.tw/Union-ClosedSetsConjecture.html

主題分類