The union-closed sets conjecture almost holds for almost all random bipartite graphs

详细信息    查看全文

• 作者：Henning Bruhn ^{bruhn@math.jussieu.fr" class="auth_mail" title="E-mail the corresponding author} ; Oliver Schaudt ^{schaudto@uni-koeln.de" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：59
• 期：Complete
• 页码：129-149
• 全文大小：480 K

文摘

Frankl’s union-closed sets conjecture states that in every finite union-closed family of sets, not all empty, there is an element in the ground set contained in at least half of the sets. The conjecture has an equivalent formulation in terms of graphs: In every bipartite graph with least one edge, both colour classes contain a vertex belonging to at most half of the maximal stable sets.

We prove that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankl’s conjecture.