12 февраля в 18:30 (МСК) на  Большом семинаре CombGeoLab выступит Nikhil Bansal с докладом о недавнем прорыве в Combinatorial Discrepancy: продвижении в гипотезе Комлоша и доказательстве 40-летней гипотезы Бека–Фиалы для широкого диапазона параметров.

Title: On Beck-Fiala and Komlós Conjectures

Abstract: 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.

Ссылка на доклад (12 февраля 18:30 МСК):
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1

Доклад будет интересен всем, кто интересуется вероятностными методами, алгоритмическими аспектами и применением линейной алгебры в комбинаторике.