Abstract

The Galvin problem asks for the minimum size of a family choose  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 ofand 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

Wednesday, Nov. 26, 14:00--15:00

Speaker

Joseph Swernofsky

Room

Room 602