Anand Srivastav Kiel University Germany

Description: One-Sided Multicolor Discrepancy of Hyperplanes over Finite Fields

Anand Srivastav
Kiel University

We investigate the multicolor discrepancy and the one-sided
multicolor discrepancy of linear hyperplanes in the
finite vector space $F_{q}^{r}$.
We show that the one-sided discrepancy
is bounded from below
by $\Omega_{q}\left(\sqrt{n/c}\right)$, $c$ the number of colors, using
Fourier analysis on $\mathbb{F}_{q}^{r}$.
We also show an upper bound of
of $O_{q}(\sqrt{n\log c})$. The upper bound is derived by
the $c$--color extension of Spencer's six standard deviation theorem
and is also valid for the one-sided discrepancy.
Thus, the gap between the upper and lower bound for the one-sided
is a factor of $\sqrt{c\log c}$ and the bounds are tight for any
constant $c$ and $q$. For large $c$, more
precisely for $c\geq qn^{1/3}$, we reduce this gap to a factor
of $\sqrt{\log c}$. All together this exhibits a new example of
a hypergraph with (almost) sharp discrepancy bounds.
Location: Ramanujan Hall, Department of Mathematics
Date: Tuesday, November 28, 2017
Time: 11:00am-12:00pm IST
Duration: 1 hour
Access: Public