webcal

Description

One-Sided Multicolor Discrepancy of Hyperplanes over Finite Fields

Anand Srivastav
Kiel University
Germany

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

Anand Srivastav Kiel University Germany