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.

Answer 2

If you're like me you're wondering how people came up with the potential, you can reduce it to another thing with a clever potential function but hopefully one you're familiar with. Also this is a chance for me to practice the hedgehog algorithm :). I will ignore consts and assume $n>4ln(m)$ for simplicity. At the end of the post I will mention some general intuition, but it will be easier to process it after seeing the proof.

In online optimization, one has the multiplicative weights algorithm. I will be using the notation of https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/ and I suggest reading the first 2 blogposts (so the link and the next one). Luca even provides nice intuition for the algorithm in blogpost 3.

In any case we do the usual trick- the edges will represent the cost functions represening loss. More specifically since we want two sided control so we will need to duplicate it. I will now be formal:

At time $t$, we define $f^t_1,..,f^t_{2m}$ - so that there are $2m$ experts. Index the edges $e_1 ,..,e_m$. We will be giving our vertices $x_1,..,x_n$ values along the times $t=1,..,n$ one by one.

For $i=1,..,m$, at time $t$ we define $f_i$ to be $x_t$ for $x_t \in \{-1,1\}$ to be decided if $x_t \in e(i)$, and zero otherwise. Similiarly for $j=m+i$ with $i=1,..,m$, except now we put $-x_t$ instead of $x_t$.

It is easy to see that we can always choose $x_t$ so that the algorithm loses a nonnegative amount.

By the regret bound for $T=n$, we get at the end that for each edge, the sum of its vertices at least $-\sqrt{nln(2m)}$, and the sum of minus its vertices is at least $-\sqrt{nln(2m)}$, giving a bound of $\sqrt{nln(2m)}$ on the discpercancy (this seems to be better by a factor of $2$ from the above answer, so hopefully I did not make a mistake).

Now for some explanation for what's going on (this is mostly repeating stuff from the blog post but this might be useful)-

The online learning algorithm allows us to do something amazing- as long as we can adaptively(!) be able to deal local (in terms of doing turn by turn) punches on distributions on a family of functions (a punch means the weighted sum is large), our local punches are guaranteed to combine into a global punch onto each single function.

Here we wanted a global values for the $x_i$ that have large sum of each edge (and so does the minus, but this is just a 'trick'), so we just needed to be able to prove we enlarge locally the weighted sum of ALL edges and antiedges, which was easy by an average argument.