Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most:

$$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \right\rfloor}\right)\frac{n^2}{2}$$

unordered couples of sets in it with at least one element in common?

If that is not possible, and if we build a graph such that every vertex represents a set and any edge exists if and only if the two corresponding sets have an element in common, by Turán's theorem there will be a $K_{\lceil \frac{n}{2} \rceil}$ complete subgraph in it, and therefore a subfamily of $\mathcal{F}$ of size $\lceil \frac{n}{2} \rceil$ where each unordered couple of sets has an element in common. Maybe from that subfamily it will be then possible to build another subfamily of size $\lceil \frac{n}{2} \rceil$ with the same element in common among all sets.

Note that every union closed family with $n$ sets and without the empty set has at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element in common, because for every couple without an element in common $\{A,B\}$ we can build two unique other couples $\{A,A \cup B\}$ and $\{B,A \cup B\}$ with non-empty intersection. However $\frac{2}{3}\binom{n}{2}$ is bigger than the above value only for $n \lt 7$.

Since a family as required by the question would imply that there are $\frac{n^2}{2\lfloor \frac{n-1}{2} \rfloor} \gt n$ unordered couples of sets with empty intersection, maybe it is possible to show that these couples would generate more than $n$ sets, or that to build those couples we need more than the maximum number of elements ($\frac{n-1}{4}$) required for a possible counterexample of the union closed sets conjecture.


1 Answer 1


Well, thinking more carefully I have found the simple counterexample given by the powerset on $n$ elements without the empty set, $\mathcal{P}([n]) \setminus \emptyset$, for $n \ge 4$.

I have decided not to delete the question just in case someone finds a useful restriction on the family properties.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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