# Conjecture about union-closed families of sets - attempt 2

[Update: this one has been disproved, but I have started conjecture attempt 3]

My previous question had an error, I am sorry for that. 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+1)/2 \rceil = n - \lceil n/2 \rceil + 1$$ 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}$$.

Note that the intersection of all sets in $$\mathcal{H}$$ gives the set of all elements of $$U(\mathcal{F})$$ that belong to at least $$\lceil n/2 \rceil$$ sets of $$\mathcal{F}$$ (so-called abundant elements, explanation here).

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, 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, here over the counterexample to the previous wrong conjecture (again satisfied with $$| \mathcal{H} | - 1$$ sets).

To get a counterexample to the current version of your conjecture, set $$t=2$$ and $$s=6$$ in the following generalization of my counterexample to your previous question.

Theorem 1. Given $$t\in\mathbb N$$ and $$\varepsilon\gt0$$, we can construct a nonempty finite union-closed family $$\mathcal F$$ of nonempty sets with a subfamily $$\mathcal H\subseteq\mathcal F$$ satisfying the conditions:
(i) $$H\in\mathcal H\implies\frac{|\mathcal P(H)\cap\mathcal F|}{|\mathcal F|}\gt\frac23-\varepsilon$$;
(ii) $$F\in\mathcal F\setminus\mathcal H\implies\frac{|\mathcal P(F)\cap\mathcal F|}{|\mathcal F|}\lt\frac13$$;
(iii) $$F\in\mathcal F\implies|\{H\in\mathcal H:F\not\subseteq H\}|\ge t$$.

Proof. Choose $$s\in\mathbb N$$ so that $$\frac{2s+1}{3s+3t+1}\gt\frac23-\varepsilon$$.

Choose disjoint sets $$A,B,C,X,Y,Z$$ with $$|A|=|B|=|C|=s$$ and $$|X|=|Y|=|Z|=t$$; let $$A=\{a_1,\dots,a_s\}$$, $$B=\{b_1,\dots,b_s\}$$, $$C=\{c_1,\dots,c_s\}$$, $$X=\{x_1,\dots,x_t\}$$, $$Y=\{y_1,\dots,y_t\}$$, $$Z=\{z_1,\dots,z_t\}$$.

For $$i=0,1,\dots,s-1$$ define:
$$A_i=X\cup B\cup C\cup\{a_j:j\le i\}$$;
$$B_i=Y\cup A\cup C\cup\{b_j:j\le i\}$$;
$$C_i=Z\cup A\cup B\cup\{c_j:j\le i\}$$.

For $$i=0,1,\dots,t-1$$ define:
$$X_i=Y\cup Z\cup A\cup B\cup C\cup\{x_j:j\le i\}$$;
$$Y_i=X\cup Z\cup A\cup B\cup C\cup\{y_j:j\le i\}$$;
$$Z_i=X\cup Y\cup A\cup B\cup C\cup\{z_j:j\le i\}$$.

Finally, define
$$T=X\cup Y\cup Z\cup A\cup B\cup C$$
and let
$$\mathcal F=\{A_j:0\le j\lt s\}\cup\{B_j:0\le j\lt s\}\cup\{C_j:0\le j\lt s\}\cup\{X_j:0\le j\lt t\}\cup\{Y_j:0\le j\lt t\}\cup\{Z_j:0\le j\lt t\}\cup\{T\}$$.

Then $$\mathcal F$$ is a union-closed family with $$|\mathcal F|=3s+3t+1$$. Let
$$\mathcal H=\{X_j:0\le j\lt t\}\cup\{Y_j:0\le j\lt t\}\cup\{Z_j:0\le j\lt t\}\cup\{T\}\subset\mathcal F.$$

(i) $$H\in H\implies\frac{|\mathcal P(H)\cap\mathcal F|}{|\mathcal F|}\ge\frac{2s+1}{3s+3t+1}\gt\frac23-\varepsilon$$;
(ii) $$F\in\mathcal F\setminus\mathcal H\implies\frac{|\mathcal P(F)\cap\mathcal F|}{|\mathcal F|}\le\frac s{3s+3t+1}\lt\frac13$$;
(iii) $$\{H\in\mathcal H:A_0\not\subseteq H\}\supseteq\{X_0,\dots,X_{t-1}\}$$,
$$\{H\in\mathcal H:B_0\not\subseteq H\}\supseteq\{Y_0,\dots,Y_{t-1}\}$$,
$$\{H\in\mathcal H:C_0\not\subseteq H\}\supseteq\{Z_0,\dots,Z_{t-1}\}$$.

Theorem 2. Given $$k\in\mathbb N$$ and $$\varepsilon\gt0$$, we can construct a nonempty finite union-closed family $$\mathcal F$$ of nonempty sets so that, for each set $$F\in\mathcal F$$, there are $$k$$ distinct sets $$H_1,\dots,H_k\in\mathcal F$$ with $$\frac{|\mathcal P(H_i)\cap\mathcal F|}{|\mathcal F|}\gt1-\varepsilon$$ and $$F\not\subseteq H_i$$.

Proof. Inasmuch as the relevant properties of $$\mathcal F$$ depend only on the structure of $$(\mathcal F,\subseteq)$$ as a poset (in fact an upper semilattice), I will simply describe it as a poset instead of a family of sets.

Let $$t=k-1$$; choose an integer $$r\ge2$$ so that $$\frac{r-1}r\gt1-\varepsilon$$; and choose $$s\in\mathbb N$$ so that $$\frac{(r-1)s+2^{r-1}-1}{rs+rt+2^r-1}\gt1-\varepsilon$$.

Start with a Boolean algebra of order $$2^r$$; insert a chain of $$s$$ elements between each atom and $$0$$; insert a chain of $$t$$ elements between each dual atom and $$1$$; delete $$0$$ and call the resulting upper semilattice $$\mathcal F$$.

Note that $$|\mathcal F|=rs+rt+2^r-1$$. Note also that, if $$H$$ is a dual atom of the original Boolean algebra, then $$|\{F\in\mathcal F:F\le H\}|=(r-1)s+2^{r-1}-1$$, so that $$\frac{|\{F\in\mathcal F:F\le H\}|}{|\mathcal F|}=\frac{(r-1)s+2^{r-1}-1}{rs+rt+2^r-1}\gt1-\varepsilon.$$ Moreover, if $$A$$ is a minimal element of $$\mathcal F$$ (i.e., an atom of the original Boolean algebra), then there is a dual atom $$H$$ such that $$A$$ is incomparable with $$H$$ and with the $$t=k-1$$ elements that were inserted between $$H$$ and $$1$$.

Finally, to convert the upper semilattice $$\mathcal F$$ into a union-closed family of sets, identify each element $$F_0\in\mathcal F$$ with the set $$\{F\in\mathcal F:F\not\ge F_0\}$$

• Thank you! I have started now attempt 3. I think it can't be restricted more than that. I think also that the requirement that the empty set is not in the family should not be relevant. Commented May 11 at 8:02
• This version of the conjecture was disproved with $25$ sets, so maybe it can be shown that attempt 3 needs more than $53$ sets, the current lower bound for a counterexample of the union-closed sets conjecture. Commented May 11 at 8:19
• You can disprove this conjecture with $23$ sets if you don't mind $\varnothing$ being one of the sets.
– bof
Commented May 11 at 18:55