# Looking for a counterexample for a conjecture about union-closed families of sets

(I have posted a corrected version of this question. The limit $$\lceil n/2 \rceil$$ must be replaced with $$\lceil (n+1)/2 \rceil$$.)

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $$\mathcal{F}$$ of $$n$$ finite sets with $$\mathcal{F} \not = \{ \emptyset \}$$.

Let $$\mathcal{H} \subseteq \mathcal{F}$$ be the family of all sets in $$\mathcal{F}$$ which are (not necessarily proper) supersets of at least $$\lceil n/2 \rceil$$ of the sets in $$\mathcal{F}$$.

I conjecture that there always exists a non-empty set in $$\mathcal{F}$$ which is a subset of at least $$| \mathcal{H} | - 1$$ of the sets in $$\mathcal{H}$$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $$| \mathcal{H} | - 1$$ sets in $$\mathcal{H}$$ and not for all of them.

• I downvoted. Your terminology is bad. Do you mean $\mathcal{H} \subseteq \mathcal{P}(\mathcal{F})$ instead? You shouldn't keep saying "sets"; you should say, e.g., "collections" when referring to things like $\mathcal{F}$. Anyways, I have no idea how $\mathcal{H}$ is defined. If $\mathcal{F} = \{\emptyset,\{1\},\{2\},\{1,2\}\}$, what is $\mathcal{H}$? I would vote to close your question. Commented May 8 at 12:47
• @mathworker21 The terminology seems correct and clear to me. A slight ambiguity is due to the verb "to contain" which is commonly used both in the sense of "as a subset" (like here, as I understand) and "as an element". I guess you would prefer "include". Commented May 8 at 13:41
• I may be wrong, but it seems very clear to me. As I wrote: read "containing" = "containing as a subset". In the above example $n=4$ and $\mathcal{H}=\{ \{1\},\{2\},\{1,2\}\}$. Consider e.g. the set $H=\{1,2\}\in\mathcal F$. It includes as subsets all the $4$ elements of $\mathcal F$, more than $4/2$, so $H\in\mathcal H$. The empty set only includes $1$ element of $\mathcal F$, $1$ is less than $4/2$, so $\emptyset\notin \mathcal H$. Commented May 8 at 13:53
• @PietroMajer: ah, okay, that does clarify, thanks! EDIT: I edited the question to hopefully make its meaning crystal clear. Commented May 8 at 13:55
• @PietroMajer Thanks for clarifying. [Now that I understand what "contain" is referring to, I think it's much better than "include" though :P] Commented May 8 at 17:43

Counterexample with $$|\mathcal F|=n=20$$. First partition the set $$[18]=\{1,2,3,\dots,18\}$$ into the disjoint sets
$$A=\{1,2,3,4\}$$, $$B=\{5,6,7,8\}$$, $$C=\{9,10,11,12\}$$,
$$X=\{13,14\}$$, $$Y=\{15,16\}$$, $$Z=\{17,18\}$$. Now define
$$\mathcal F=\{\varnothing,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3,C_0,C_1,C_2,C_3,X_0,X_1,Y_0,Y_1,Z_0,Z_1,T\}$$ where:
$$A_0=B\cup C\cup Z$$, $$A_1=A_0\cup\{1\}$$, $$A_2=A_1\cup\{2\}$$, $$A_3=A_2\cup\{3\}$$,
$$B_0=A\cup C\cup Y$$, $$B_1=B_0\cup\{5\}$$, $$B_2=B_1\cup\{6\}$$, $$B_3=B_2\cup\{7\}$$,
$$C_0=A\cup B\cup X$$, $$C_1=C_0\cup\{9\}$$, $$C_2=C_1\cup\{10\}$$, $$C_3=C_2\cup\{11\}$$,
$$X_0=A\cup B\cup C\cup Y\cup Z$$, $$X_1=X_0\cup\{13\}$$,
$$Y_0=A\cup B\cup C\cup X\cup Z$$, $$Y_1=Y_0\cup\{15\}$$,
$$Z_0=A\cup B\cup C\cup X\cup Y$$, $$Z_1=Z_0\cup\{17\}$$,
$$T=A\cup B\cup C\cup X\cup Y\cup Z=[18]$$.

To see that $$\mathcal F$$ is union-closed and $$|\mathcal F|=20$$, observe that:
$$\varnothing\subsetneqq A_0\subsetneqq A_1\subsetneqq A_3$$,
$$\varnothing\subsetneqq B_0\subsetneqq B_1\subsetneqq B_3$$,
$$\varnothing\subsetneqq C_0\subsetneqq C_1\subsetneqq C_3$$,
$$A_0\cup B_0=X_0\subsetneqq X_1\subsetneqq T$$,
$$A_0\cup C_0=Y_0\subsetneqq Y_1\subsetneqq T$$,
$$B_0\cup C_0=Z_0\subsetneqq Z_1\subsetneqq T$$,
$$A_0\cup B_0\cup C_0=T$$.

Finally, $$\mathcal H=\{X_0,X_1,Y_0,Y_1,Z_0,Z_1,T\}$$, so $$|\mathcal H|=7$$, while each of the minimal nonempty elements of $$\mathcal F$$, namely $$A_0$$, $$B_0$$, and $$C_0$$, is contained in just $$5$$ elements of $$\mathcal H$$.

• Is that unusual? I definitely don't carefully check the details of every MO post I upvote... just try to discern whether real effort has been put into it and whether it is likely to make a positive contribution. Anyways I guess this is getting a bit off topic from the question at hand... Commented May 10 at 14:11
• I checked it and it is correct! Thank you very much. I will study this example to see if it is interesting regarding to the linked question. By the way if we remove the empty set the family satisfies the conjecture. So it would be nice to have a counterexample without the empty set. Commented May 10 at 14:17
• Also, this family with or without the empty set is not independent, so maybe I will ask in the future another question with that restriction, since it suffices to prove the union-closed sets conjecture for independent families (extension of the separating property). Thank you very much anyway. Commented May 10 at 14:34
• I realized now that I made a mistake in the question. The $\lceil n/2 \rceil$ limit is correct for $n$ odd but needs to be $\lceil (n+1)/2 \rceil$ for $n$ even. In other words it needs to be $n-\lceil n/2 \rceil+1$ for $n$ odd or even. Should I correct the question or start another one? This is because the intersection of all $H_i$ has to give the set of all the abundant elements. Commented May 10 at 15:02
• I think a separated question should be better - let this one be dedicated to counterexamples :) Commented May 10 at 15:13

The following non-counterexample (it had a mistake) can serve to show that the factor $$1/2$$ can’t be lowered.

Consider for instance, for $$r\in \mathbb N$$, the family $$\mathcal F:=\{F\subset[2r]: |F|\ge r\}$$, so that $$n:=|\mathcal F|=\sum_{i\ge r}{2r\choose i}=2^{2r-1}+\frac12{2r\choose r}$$. Then in $$\mathcal H$$ there are all $$H\in\mathcal F$$ of cardinality $$|H|= 2r-1$$, because every such $$H$$ includes $$\sum_{i\ge r}{2r-1\choose i}=2^{2r-2}\sim\frac n2$$ sets $$F\in\mathcal F$$. But every $$F\in\mathcal F$$ fails to be a subset of at least $$r$$ elements $$H$$ of $$\mathcal H$$, namely $$H_i:=[2r]\setminus \{i\}$$ for $$i\in F$$.

• Are you sure? I think it should be $\sum_{i\ge r}{2r-1\choose i}=2^{2r-2}$ (see here) or am I missing something? Commented May 8 at 14:28
• yes, I wrongly did $\sum _{i\le r}$ ! deleting Commented May 8 at 14:39
• well I edited to keep it, as at least it shows that n/2 can’t be improved Commented May 8 at 15:00
• @PietroMajer Sorry, what factor $1/2$ are you referring to? Why doesn't your answer disprove the OP's conjecture? They ask to show there's some set in $\mathcal{F}$ which is a subset of all but at most one set in $\mathcal{H}$. In your answer $|\mathcal{H}| = 2r$ and each $F \in \mathcal{F}$ is a subset of at most $r$ sets $H \in \mathcal{H}$. Commented May 8 at 17:43
• Yes but here for each set $H\in\mathcal H$ there are approximatively $\frac12 n$ subsets $F\subset H$, $F\in\mathcal F$, yet less than $\frac12 n$, which was required. Commented May 8 at 18:13