In a paper published by Bruhn and Schaudt, as well as in a presentation given by Bruhn, they point out how the union-closed sets conjecture is tight for power sets, implying it is still open. I am confused however, as I have not come across any literature regarding the conjecture for power sets, so I am wondering if someone can elucidate why this is the case? Is it because the result is already proven for power sets?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is trivially true for power sets, since these are union-closed families with $2^n$ sets such that every element appears in exactly $2^{n-1}$ sets.
This is what they mean by the conjecture being tight - power sets show that the $1/2$ of the conjecture cannot be increased to any greater constant.
answered Oct 20, 2019 at 18:25