Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Three permutations, simplified

Cole Franks, Rutgers

Location:  Hill 705
Date & time: Monday, 04 March 2019 at 2:00PM - 3:00PM

Abstract: A k-permutation family on n vertices is a set system consisting of the intervals of k permutations of [n]. Both 1- and 2-permutation families have discrepancy 1, that is, one can color the vertices red and blue such that the number of reds and blues in each edge differs by at most one. That is, their discrepancy is bounded by one. Beck conjectured that the discrepancy of for 3-permutation families is also O(1), but Newman and Nikolov disproved this conjecture in 2011. We give a simpler proof that Newman and Nikolov's sequence of 3-permutation families has discrepancy at least logarithmic in n. We also exhibit a new, tight lower bound for the related notion of root-mean-squared discrepancy of a 6-permutation family.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.