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.


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.