Minimal majority sequences

Computer Science/Discrete Mathematics Seminar II
Topic:Minimal majority sequences
Speaker:Noga Alon
Affiliation:Tel Aviv University; Visiting Professor, School of Mathematics
Date:Tuesday, October 15
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1015-NogaAlon

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.