Аннотация:

A conjecture of Komlós states that the discrepancy of any collection of unit vectors is $O(1)$, i.e., for any matrix $A$ with unit columns, there is a vector $x$ with $-1,1$ entries such that $|Ax|_\infty = O(1)$. The related Beck-Fiala conjecture states that any set system with maximum degree k has discrepancy $O(k^{1/2})$.

I will describe an $O((\log n)^{1/4})$ bound for the Komlós problem, improving upon an $O((\log n)^{1/2})$ bound due to Banaszczyk. Time permitting, we will see how these ideas can be used to resolve the Beck-Fiala conjecture for $k >= (\log n)^2$.

Запись доклада: