Simultaneous systems of representatives for families of finite sets

Abstract:

Let $h \geq 2$ and $k \geq 1$. Then there exists a real number $\lambda = \lambda \left ( {h,k} \right ) \in \left ( {0,1} \right )$ such that, if $\mathcal {S} = \left \{ {{S_i}} \right \}_{i = 1}^s$ and $\mathcal {T} = \left \{ {{T_j}} \right \}_{j = 1}^t$ are families of nonempty, pairwise disjoint sets with $|{{S_i}}| \leq h$ and $|{{T_j}}| \leq k$ and ${S_i} \nsubseteq {T_j}$ for all $i$ and $j$, then $N\left ( {\mathcal {S},\mathcal {T}} \right ) \leq {h^s}{\lambda ^t}$, where $N\left ( {\mathcal {S},\mathcal {T}} \right )$ is the number of sets $X$ such that $X$ is a minimal system of representatives for $\mathcal {S}$ and $X$ is simultaneously a system of representatives for $\mathcal {T}$. A conjecture about the best possible value of the constant $\lambda \left ( {h,k} \right )$ is proved in the case $h > k$. The necessity of the disjointness conditions for the families $\mathcal {S}$ and $\mathcal {T}$ is also demonstrated.