Title: Vector discrepancy
Speaker: Alex Nikolov, Rutgers
Date: Tuesday, March 27, 2012 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
For a set system F of m subsets of [n] and an assignment chi:[n] --> {+1, -1}, the discrepancy of chi on F is defined as the maximum over S in F of the absolute value of sum_{e in S}{chi(e)}. The combinatorial discrepancy of F is the minimum discrepancy of all assignments chi, and the hereditary discrepancy of F is the maximum discrepancy of any induced subsystem of F. An important open problem in combinatorial discrepancy theory is to prove tight upper and lower bounds on the discrepancy of set systems of maximum degree bounded by t.
Beck and Fiala conjectured that the right bound is O(sqrt{t}). We consider a relaxation of discrepancy, where each element of [n] is assigned a unit vector in R^n and the discrepancy of an assignment is the maximum over S in F of the Eucliden norm of the sum of vectors assigned to the elements of S. Recently Nikhil Bansal showed an upper bound on hereditary discrepancy in terms of hereditary vector discrepancy, and Jiri Matousek used this result to show that the determinant lower bound of Lovasz, Spencer, and Vesztergombi on hereditary discrepancy is almost tight. We will briefly survey these results and prove the vector discrepancy variant of the Komlos conjecture, which implies that the vector discrepancy of set systems of maximum degree bounded by t is at most sqrt{t}, i.e. the vector discrepancy variant of the Beck-Fiala conjecture. The original Komlos and Beck-Fiala conjectures remain open.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math