Skip to main content
5 of 20
added 139 characters in body

Lower bound for the number of some couples of sets in an intersection-closed family

Let $\mathcal{F}$ be a family of $n$ finite sets. The family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is intersection-closed ($\mathcal{F}$ must contain at least one instance of $A \cap B$ for any $A,B \in \mathcal{F}$);
  2. every element in $U(\mathcal{F})$ belongs to at least $\lceil (n-1)/2 \rceil$ sets of $\mathcal{F}$ (every set is counted with its multiplicity);
  3. every possible singleton set belongs to $\mathcal{F}$, i.e. if $a \in U(\mathcal{F})$ then $\{a\} \in \mathcal{F}$.

Let $c(\mathcal{F})$ be the number of unordered couples $\{A, B\}$, $A, B \in \mathcal{F}$, $A \cup B = U(\mathcal{F})$, counted with multiplicity of the respective sets (i.e. if $A$ has multiplicity $n$ and $B$ has multiplicity $m$ then we count $nm$ such couples).

Can we get a lower bound for $c(\mathcal{F})$ for any possible choice of $\mathcal{F}$?

Or at least prove that $c(\mathcal{F}) \ge 1$?

[I have a posted a slightly simplified version of this question at math.stackexchange]