Login |

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

Location: | Ramanujan Hall, Department of Mathematics |

Date: | Tuesday, November 28, 2017 |

Time: | 11:00am-12:00pm IST |

Duration: | 1 hour |

Access: | Public |