Motivated by questions in Social Choice Theory I will consider the
following extremal problem in Combinatorial Geometry.
Call a sequence of vectors of length n with -1,1 entries feasible if it
contains a subset whose sum is positive in more than n/2 coordinates. Let
g(n,m) denote the minimum number g so that any feasible sequence of m
vectors contains a subset of size at most g whose sum is positive in more
than n/2 coordinates, and put G(n)=sup g(n,m) where the supremum is
taken over all values of m.
The study of the asymptotic behavior of G(n) combines geometric and
combinatorial ideas with tools from linear algebra and discrepancy
theory, and is related to results of Huckeman, Jurkat and Shapley
on indecomposable hypergraphs, of Graham and Sloane on anti-Hadamard
matrices, of Hastad on threshold gates requiring large weights and of
Vu and myself on a coin weighing problem.
Joint work with Bredereck, Chen, Kratsch, Niedermeier and Woeginger.