Colorings of $k$-sets with low discrepancy on small sets

Abstract

For $0<\delta \le 1$, let $R_k(m;\delta )$ denote the smallest $N$ such that every coloring of $k$-element subsets by two colors yields an $m$-element set $M$ with relative discrepancy $\delta$, which means that one color class has at least $(\frac{1+\delta }{2})\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ elements. The number $R_k(m;\delta )$ may be viewed as an extension of the usual $k$-hypergraph Ramsey number because $R_k(m)=R_k(m,1)$. Our main result is the following theorem. %\begin{theorem} For some constants $c,k_0$, and $\eps>0$, and for all $k\ge k_0$, $c\log k\le n\le k/11$, \[ R_k(k+n);2^{-\eps n})\geq \tw_{\lfloor k/n\rfloor}(2). \] %\end{theorem} In particular, for $n=\lceil c\log k\rceil$, we get a tower of height $\delta k/\log k$ and relative discrepancy polynomial in~$k$.