\(d\)-Galvin families (Q2294104)

Summary: The Galvin problem asks for the minimum size of a family \(\mathcal{F} \subseteq \binom{[n]} {n/2}\) with the property that, for any set \(A\) of size \(\frac n 2\), there is a set \(S \in \mathcal{F}\) which is balanced on \(A\), meaning that \(|S \cap A| = |S \cap \overline{A}|\). We consider a generalization of this question that comes from a possible approach in complexity theory. In the generalization the required property is, for any \(A\), to be able to find \(d\) sets from a family \(\mathcal{F} \subseteq \binom{[n]} {n/d}\) that form a partition of \([n]\) and such that each part is balanced on \(A\). We construct such families of size polynomial in the parameters \(n\) and \(d\).