聯集封閉集合中的高頻元素

Abstract

聯集封閉集合猜想（Union-Closed Sets Conjecture）提出：對於任意一個聯集封閉的集合族 $\F$，是否總存在一個元素，包含於至少一半的集合中。2022 年，Nagel 推出此猜想的一個推廣版本，提出在一個聯集封閉集合族中，第 $k$ 常出現的元素應出現在至少 $\frac{1}{2^{k-1} + 1} |\F|$ 個集合中。

本文結合了 Gilmer 的亂度法與 Knill 的組合論證，證明了對於所有 $k \ge 2$，Nagel 的推廣猜想皆成立。此外，我們亦證明，當 $|\F| \to \infty$ 時，第 $k$ 常見的元素至少會出現在 $\left( \frac{3 - \sqrt{5}}{2} - o(1) \right) |\F|$ 個集合中，反映出聯集封閉集合猜想近期研究所取得的進展。

The Union-Closed Sets Conjecture asks whether every union-closed set family $\F$ has an element contained in $\frac12 |\F|$ of its sets. In 2022, Nagel posed a generalisation of this problem, suggesting that the $k$th most popular element in a union-closed set family must be contained in at least $\frac{1}{2^{k-1} + 1} |\F|$ sets.

We combine the entropic method of Gilmer with the combinatorial arguments of Knill to show that this is indeed the case for all $k \ge 2$. Furthermore, we show that when $|\F| \to \infty$, the $k$th most frequent element will appear in at least $\left( \frac{3 - \sqrt{5}}{2} - o(1) \right) |\F|$ sets, reflecting the recent progress made for the Union-Closed Set Conjecture.