A simplified disproof of Beck's three permutations conjecture and an application to root-mean-squared discrepancy
From MaRDI portal
Publication:6309154
DOI10.1017/S0963548320000474zbMath1507.05006arXiv1811.01102WikidataQ123362727 ScholiaQ123362727MaRDI QIDQ6309154
Publication date: 2 November 2018
Abstract: A $k$-permutation family on $n$ vertices is a set system consisting of the intervals of $k$ permutations of the integers $1$ through $n$. The discrepancy of a set system is the minimum over all red-blue vertex colorings of the maximum difference between the number of red and blue vertices in any set in the system. In 2011, Newman and Nikolov disproved a conjecture of Beck that the discrepancy of any $3$-permutation family is at most a constant independent of $n$. Here we give a simpler proof that Newman and Nikolov's sequence of $3$-permutation families has discrepancy $Omega(log n)$. We also exhibit a sequence of $6$-permutation families with root-mean-squared discrepancy $Omega(sqrt{log n})$; that is, in any red-blue vertex coloring, the square root of the expected difference between the number of red and blue vertices in an interval of the system is $Omega(sqrt{log n})$.
This page was built for publication: A simplified disproof of Beck's three permutations conjecture and an application to root-mean-squared discrepancy
