3
$\begingroup$

Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element in common. This is because for every couple without an element in common $\{A,B\}$ we can build two other couples $\{A,A \cup B\}$ and $\{B,A \cup B\}$ with non-empty intersection between the two sets, and also $\{A,A \cup B\} = \{A,A \cup C\}$ implies $B = C$ when $A \cap B = \emptyset$ and $A \cap C = \emptyset$.

The bound is tight for $n = 3$. However, is it possible to improve it for $n$ bigger than some value? For example to $\frac{3}{4}\binom{n}{2}$? Or to some $f(n)\binom{n}{2}$ with $f(n)$ increasing? Might considering only the possible counterexamples of the union closed sets conjecture help?

$\endgroup$

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.