\(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
    0 references
    0 references
    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

    Identifiers