Is the bound of Spencer on discrepancy tight?

Question

Suppose $\mathcal{S} = \{S_1,\ldots,S_m\}$ is a set system in $[n]=\{1,\ldots,n\}$, which means that for each $i$, $S_i\subset [n].$ Define the discrepancy of $\mathcal{S}$ by $$disc(\mathcal{S})=\min_{\chi}\max_{i=1,\ldots,m}|\chi(S_i)|,$$ where $\chi:[n]\to \{-1,+1\}$ is a coloring and for a subset $S$ of $[n$], denote $\chi(S)=\sum_{j\in S}\chi(j)$. Spencer proved that for all set system $\mathcal{S} = \{S_1,\ldots,S_m\}$ with $m\geq n$, $$disc(\mathcal{S})=O(\sqrt{n\ln(2m/n})$$ in "Six Standard Deviations Suffice".

Is the result tight? In other words, whether there exsits a set system $\mathcal{S} = \{S_1,\ldots,S_m\}$ such that $disc(\mathcal{S})=\Omega(\sqrt{n\ln(2m/n})$?

Some books mentioned there exists such a set system only for $m=n$. Like "The Probabilistic Method" by Alon and Spencer, "Geometric Discrepancy" by Matousek. I cannot find a proof for general $m>n$.

Answer 1

Yes, the bound is tight, and here is a proof sketch. In fact, we will show that a random sequence of subsets $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ provides the lower bound up to constants. Precisely, sample each $S_i$ just by including each element of $[n]$ in the set with probability $1/2$.

We assume $n, m$ are large. Fix a coloring $\chi: [n] \to \{-1, 1\}$. Note that the distribution of $\chi(S_i)$ is approximately normal with variance $\Theta(\sqrt{n})$. Therefore, $\mathrm{Pr}_{S_i}[\chi(S_i) \le c\sqrt{n\log(2m/n)}] \le 1 - \frac{n}{m}$ for a small constant $c$. Therefore, $$\Pr_\mathcal{S}[\mathrm{disc}(\mathcal{S}) \le c\sqrt{n\log(2m/n)}] \le \left(1-\frac{n}{m}\right)^m < \exp(-n).$$ This suffices to union bound over all $2^n$ colorings $\chi$.