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$.
@article{10_37236_8432,
author = {Johan H\r{a}stad and Guillaume Lagarde and Joseph Swernofsky},
title = {\(d\)-Galvin families},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/8432},
zbl = {1432.05113},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8432/}
}
TY - JOUR
AU - Johan Håstad
AU - Guillaume Lagarde
AU - Joseph Swernofsky
TI - \(d\)-Galvin families
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8432/
DO - 10.37236/8432
ID - 10_37236_8432
ER -
%0 Journal Article
%A Johan Håstad
%A Guillaume Lagarde
%A Joseph Swernofsky
%T \(d\)-Galvin families
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8432/
%R 10.37236/8432
%F 10_37236_8432
Johan Håstad; Guillaume Lagarde; Joseph Swernofsky. \(d\)-Galvin families. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8432
