TITLE: Disrepancy games
SPEAKER: Michael Krivelevich
WHEN: March 2, 4:30pm
WHERE: PPB 300
ABSTRACT:
A discrepancy game played on a hypergraph $H=(V,E)$ by two players, Balancer and Unbalancer. They select one element of the vertex set $V$ alternately, until all vertices are selected. Balancer wins if at the end of the game all edges $e$ in $E$ are roughly equally distributed between the two players.
We derive a criteria for Balancer’s win in a general discrepancy game. In particular, it follows from our result that if $H$ is $n$-uniform and has $m$ edges, then Balancer can achieve having between $n/2-c\sqrt{n\ln m}$ and $n/2+c\sqrt{n\ln m}$ of his vertices on every edge $e$ of $H$.
We also discuss applications in positional game theory.
A joint work with Noga Alon, Joel Spencer and Tibor Szab\’o.
