Abstract
The Galvin problem asks for the minimum size of a familychoose with the property that, for any set A of size, there is a set S in F which is balanced on A, meaning that. 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 choose n/d that form a partition of and such that each part is balanced on A. We construct such families of size polynomial in the parameters n and d.
This is joint work with Johan Håstad and Guillaume Lagarde.
Time
2025-11-26 14:00 - 15:00
Speaker
Joseph Swernofsky, KTH Royal Institute of Technology
Room
Room 602
