System of unbiased representatives for a collection of bicolorings

摘要

Let B denote a set of bicolorings of [n], where each bicoloring is a mapping of the points in [n] to {-1, +1}. For each B is an element of B, let Y-B = (B(1), ..., B(n)). For each A subset of [n], let X-A is an element of {0, 1}(n) denote the incidence vector of A. A non-empty set A is said to be an 'unbiased representative' for a bicoloring B is an element of B if < X-A, Y-B >= 0. Given a set B of bicolorings, we study the minimum cardinality of a family A consisting of subsets of [n] such that every bicoloring in B has an unbiased representative in A. (C) 2019 Elsevier B.V. All rights reserved.