Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653201 | European Journal of Combinatorics | 2017 | 21 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Henning Bruhn, Oliver Schaudt,