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

  • $\begingroup$ I added absolute values to make sure this is the standard definition of discrepancy, let me know if you meant something else. $\endgroup$ – 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.

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.