Simultaneous systems of representatives for finite families of finite sets

Abstract:

Let $h \geq 2$ and $k \geq 1$. It is proved that if $\mathcal {S} = \{ {S_i}\} _{i = 1}^s$ and $\mathcal {T} = \{ {T_j}\} _{j = 1}^t$ are two families of nonempty, pairwise disjoint sets such that $|{S_i}| \leq h,|{T_j}| \leq k$ and ${S_i} \nsubseteq {T_j}$ for all $i$ and $j$, then the number $N(\mathcal {S},\mathcal {T})$ of the 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}$ that satisfies $N(\mathcal {S},\mathcal {T}) \leq {h^s}{(1 - (h - r)/{h^{q + 1}})^t}$, where $k = q(h - 1) + r$ with $0 \leq r \leq h - 2$. This was conjectured by M. B. Nathanson [3] in 1985.