Tue, November 28, 2017
Public Access


Category:
Category: All

28
November 2017
Mon Tue Wed Thu Fri Sat Sun
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      
8:00am  
9:00am  
10:00am  
11:00am [11:00am] Anand Srivastav Kiel University Germany
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.

12:00pm  
1:00pm  
2:00pm  
3:00pm  
4:00pm  
5:00pm  
6:00pm