Computer Science/Discrete Mathematics Seminar II

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 by 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.