2
$\begingroup$

Given an union-closed family of sets $\mathcal{F}$, with $n = \vert\mathcal{F}\vert$ and thus $n \choose 2$ unordered couples of distinct sets $\{A, B\}$, $A,B \in \mathcal{F}$, I would like to compute a good lower bound for the number of couples such that $A \subset B$ or $B \subset A$ as a function of $n$, i.e.:

$$\text{Number of couples such that } A \subset B \text{ or } B \subset A \ge f(n)$$

Intuitively for a couple $\{A, B\}$ with $A \not\subset B$ and $B \not\subset A$, there are two couples $\{A, C\}$ and $\{B, C\}$, $C = A \cup B$, with $A \subset C$ and $B \subset C$, however two couples $\{A, B_1\}$ and $\{A, B_2\}$ may share the same $\{A, C = A \cup B_1 = A \cup B_2\}$, so this does not seem to help.

Any hint?

$\endgroup$
0
3
$\begingroup$

In terms of $n$ alone, and lacking any extra constraints, I think $n-1$ is the best lower bound you can get.

It is a lower bound, because if you take $A = \bigcup {\cal F}$, then for all $B \in {\cal F} \setminus \{A\}$ you have $B \subset A$, and this gives you $n-1$ pairs.

The bound is reached with the union-closed family $$ {\cal F} = A \;\cup\; \{B_i \;:\; i=1,\ldots,n-1\}, $$ where $A = \{1,2,\ldots,n-1\}$, and $B_i = A\setminus\{i\}$.

$\endgroup$

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.