# Colouring achieving simple discrepancy bound?

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$.

• I added absolute values to make sure this is the standard definition of discrepancy, let me know if you meant something else. – Sasho Nikolov Oct 14 '13 at 15:10

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.

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.