Colouring achieving simple discrepancy bound?

Question

Given a hypergraph $H$ with $n$ vertices and $m$ edges, one of the simplest inequalities on the discrepancy of $H$ is $\text{disc}(H) \le \sqrt{2n \ln (2m)}$.

This is usually proved by mixing together one type of Chernoff bound using the probabilistic method (for instance, see the outline proof at the Wikipedia article on discrepancy).

Is there a known colouring $\chi \colon V(H) \to \{-1,1\}$ of the vertices of a hypergraph $H$ with $-1$ and $1$ that witnesses this bound? In other words, such that for every edge $e \in E(H)$, $$\left|\sum_{v \in e} \chi(v)\right| \le \sqrt{2n \ln (2m)}.$$

Of course, the probabilistic method guarantees the existence of such a $\chi$, but is there an algorithm better than exhaustively checking all possible colourings?

---

For completeness, the discrepancy of a hypergraph $H$ is the minimum over all possible colourings $\chi \colon V(H) \to \{-1,1\}$ of the largest value of the local discrepancy $\left|\sum_{v \in e} \chi(v)\right|$ over all edges $e$ of $H$.

Answer 1

I assume you mean a deterministic algorithm. The best discrepancy bound is in fact $O(\sqrt{n\log (m/n)})$ which is $O(\sqrt{n})$ when $m = O(n)$. This the famous Six Standard Deviations Suffice bound of Spencer (1985 TAMS). A coloring achieving this bound can be found in deterministic polynomial time, using a recent result by Bansal and Spencer.

Achieving the random coloring bound of $\sqrt{2n \ln (2m)}$ can be done with simple classic derandomization methods. You can use the method of conditional expectations or variants of the multiplicative weights method. You can even achieve the stronger $\sqrt{2|e|\ln(2m)}$ bound for each edge $e$. See Section 1.1. of Chazelle's book.

For completeness, let me reproduce the multiplicative weights argument, because it's nice and simple. Identify the vertices of $H$ with $[n]$. We will pick $\chi(i)$ for $i = 1, \ldots, n$ greedily. Define $D(e, k) = \sum_{i \in e, i \leq k}{\chi(i)}$ to be the discrepancy of $e$ up to $k$. Let $p(e, k) = \frac{1}{2}e^{\alpha D(e, k)} +\frac{1}{2}e^{-\alpha D(e, k)}$ for $\alpha = \sqrt{2\ln (2m)/n}$, and the potential function $P(k) = \sum_e{p(e, k)}$. Define also $p(e, 0) = 1$ and $P(0) = m$. You can verify that for a random choice of $\chi(k+1)$, $\mathbb{E}P(k+1) \leq P(k)e^{\alpha^2/2}$. So you can just pick each $\chi(k)$ to minimize $P(k)$, and after the final step you have $$ \frac{1}{2} e^{\alpha |D(e, n)|} \leq \max_e p(e, n) \leq P(n) \leq me^{n\alpha^2/2}. $$

Simple algebra gives the bound.