\(d\)-Galvin families (Q2294104)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(d\)-Galvin families |
scientific article |
Statements
\(d\)-Galvin families (English)
0 references
10 February 2020
0 references
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\).
0 references
Galvin problem
0 references
complexity theory
0 references