Disjointly representing set systems (Q1873809): Difference between revisions

Let \({\mathcal F}\) be a family of \(r\)-element subsets of a finite set, and let \(\mathcal G\) be a family of disjoint \(s\)-element subsets. We say that \(\mathcal F\) is disjointly representable by \(\mathcal G\) if for any \(F\in {\mathcal F}\) there is a set \(S\in {\mathcal G}\) such that \(S\subseteq F\). Denote by \(f(r,s)\) the minimum size of a not disjointly representable family. The authors prove a lower bound \(f(r,s)>({r+s\over 50s})^{s\over s-1}\) for \(r\geq s\geq 2\) and two upper bounds for \(f(r,s)\) of the form \(f(r,s)\leq 25s^{s+1} r^{s\over s-1}\) and \(f(r,s)\leq 15({r\over s})^{s\over s-1}\log{r\over s}\). The first upper bound differs in a constant factor from the lower one if \(s=\text{const}\) and the second one holds for \(r\geq 2s\geq 4\). The first upper bound is based on a construction of \(K_{s,s!+1}\)-free graphs, while the second one is based on a probabilistic argument.