按年被提到
20222022 · 1 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:2211.09055 · math.CO

A constant lower bound for the union-closed sets conjecture

Justin Gilmer · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2022-11-19 · 最近 2023-01-03
2不同的人
2活跃月份
2讨论串
8被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We show that for any union-closed family $\mathcal{F} \subseteq 2^{[n]}, \mathcal{F} \neq \{\emptyset\}$, there exists an $i \in [n]$ which is contained in a $0.01$ fraction of the sets in $\mathcal{F}$. This is the first known constant lower bound, and improves upon the $Ω(\log_2(|\mathcal{F}|)^{-1})$ bounds of Knill and Wójick. Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if $A, B$ are independent samples from a distribution over subsets of $[n]$ such that $Pr[i \in A] < 0.01$ for all $i$ and $H(A) > 0$, then $H(A \cup B) > H(A)$.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论sischoel · 2022-11

“From skimming the paper (https://arxiv.org/abs/2211.09055), the proof seems to be amazingly short and relies only on a few theorems that one encounters in introductory class on information theory. Definitely recommendable to read if one is interested in that kind of combinatorics.”

Justin Gilmer gave a constant lower bound for the union-closed sets conjecture原评论 ↗
评论thomasahle · 2023-01

“Paper link: https://arxiv.org/abs/2211.09055 Abstract: We show that for any union-closed family F\subseeq 2^[n],F≠ {∅}, there exists an i∈[n] which is contained in a 0.01 fraction of the sets in F. This is the first known constant lower bound, and improves upon the Ω(log_2(|F|)^ {−1}) bounds of Knill and Wójick. Our result follows from an information th…”

Long out of math, an AI programmer cracks a pure math problem原评论 ↗