2013/02/28 by Bruhn, Henning, Schaudt, Oliver
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1302.7141
Frankl's union-closed sets conjecture states that in every finite union-closed set of sets, there is an element that is contained in at least half of the member-sets (provided there are at least two members). 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.