The union-closed sets conjecture states the following. Let $F$ be a finite family of finite sets that is union-closed and let $\cup (F)$ be the union of all sets in $F$. Then we can find an element in $\cup (F)$ that appears in at least half of the sets in $F$.

One can show that w.l.o.g. we can assume $F$ to be separating, that is for any two elements in $\cup (F)$ we can find a set in $F$ that contains exactly one of the two elements. So in the literature many statements concerning the conjecture are proven for separating families.

However we can do better. Say a family $F$ is given. We now chose an element in $\cup (F)$ and remove it from every set in $F$ if the number of sets doesn't decrease by doing so. We repeat this process as long as we can. After that we obtain a family $\tilde{F}$ with the following property. For every $x \in \cup(\tilde{F})$ we can find $S \in \tilde{F}$ such that $x \in S$ and $S\backslash \{x\} \in \tilde{F}$. We call families with this property minimal. It is easy to see that if $\tilde{F}$ fulfills the conjecture then so does $F$. Thus w.l.o.g. we can assume $F$ to be minimal.

Now we make the observation that being separating is strictly weaker than being minimal. Say $F$ is a minimal family and let $x, y \in \cup (F)$. Then we can find $S \in \cup (F)$ such that $x \in S$ and $S\backslash \{x\} \in F$. If $y \notin S$ then $S$ contains exactly $x$ and if $y \in S$ then $S\backslash \{x\}$ contains exactly $y$. Thus $F$ is separating. Now consider the family $\{\emptyset, \{1,2\},\{2,3\},\{1,2,3\} \}$. One can easily check that it is separating but not minimal.

This leaves me with the following questions:

Is there any literature about the union-closed sets conjecture that introduces a concept like minimal families?

If not, is an inductive proof for the union-closed sets conjecture plausible abusing minimal families (reduce the number of sets in a minimal family by removing an arbitrary element from all sets)?

Edit: Here is a follow up.


If I am understanding your idea correctly, I believe you are saying that you can suppose your family doesn't have sets of the form $S$ and $S\cup \{a\}$ for some $a\in U(\mathcal{F})$

You can check Lo Faro's paper "A note on the union-closed sets conjecture" and see that a counterexample must have some sets of that form. Otherwise you wouldn't have a minimal one.

  • $\begingroup$ Its the other way around, a minimal family $F$ MUST have sets of the form $S$ and $S\cup \{a\}$ for every $a \in \cup(F)$. $\endgroup$
    – kevkev1695
    Mar 4 '20 at 16:07
  • $\begingroup$ Yes, I am sorry. That is what I meant. In Lo Faro's paper that can be seen. If you suppose the conjecture is false and take a minimal counterexample, then if you pick any element in $U(F)$ and take it from all sets you get a new union-closed family. It has less elements in the ambient set, and so it satisfies the conjecture. If you dont lose sets, then so does $F$, which you supposed to be a counterexample. Then you must lose sets, i.e., have sets of the form $S$, $S\cup\{a\}$. In that way, he sees that a minimal counterexample must have sets of that form for all $a$. $\endgroup$ Mar 4 '20 at 18:04
  • $\begingroup$ Then I dont understand the statement, sorry. $\endgroup$
    – kevkev1695
    Mar 4 '20 at 18:07
  • $\begingroup$ If a counterexample must have sets of that form, then it is enough to prove the conjecture for those families because there would be no counterexample. $\endgroup$ Mar 4 '20 at 18:09
  • 1
    $\begingroup$ I know, I am just answering the question regarding the literature. Both papers from Lo Faro regarding the union-closed sets conjecture can be something you are looking for. About those sets, you can actually prove that you can suppose your family to have three distinct pairs of sets of the form $X$, $X\cup\{a\}$, $Y$,$Y\cup\{a\}$ and $Z\cup\{a\}$ for every $a\in U(\mathcal{F})$. $\endgroup$ Mar 4 '20 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.