<p>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 <span class="math-container">$n&gt;4ln(m)$</span> 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.</p>

<p>In online optimization, one has the multiplicative weights algorithm. I will be using the notation of <a href="https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/" rel="nofollow noreferrer">https://lucatrevisan.wordpress.com/2019/04/22/online-optimization-post-0-definitions/</a> 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.</p>

<p>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:</p>

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

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

<p>It is easy to see that we can always choose <span class="math-container">$x_t$</span> so that the algorithm loses a nonnegative amount. </p>

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

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

<p>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.</p>

<p>Here we wanted a global values for the <span class="math-container">$x_i$</span> 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.</p>

CC BY-SA 4.0
2019-09-20T20:41:36.693Z
2019-09-20T20:41:36.693Z
Andy
<p>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 <a href="http://link.springer.com/chapter/10.1007/978-3-642-23719-5_35" rel="nofollow">recent result</a> by Bansal and Spencer.</p>

<p>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 <a href="http://www.cs.princeton.edu/~chazelle/book.html" rel="nofollow">Chazelle's book</a>.</p>

<p>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}.
$$</p>

<p>Simple algebra gives the bound.</p>

CC BY-SA 3.0
2013-10-14T14:42:22.373Z
2013-10-15T14:17:16.657Z
2013-10-15T14:17:16.657Z
Sasho Nikolov
<p>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)}$.</p>

<p>This is usually proved by mixing together one type of <a href="https://en.wikipedia.org/wiki/Chernoff_bound" rel="nofollow">Chernoff bound</a> using the <a href="https://en.wikipedia.org/wiki/Probabilistic_method" rel="nofollow">probabilistic method</a> (for instance, see the outline proof at the <a href="https://en.wikipedia.org/wiki/Discrepancy_of_hypergraphs" rel="nofollow">Wikipedia article on discrepancy</a>).</p>

<p>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)}.$$</p>

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

<hr>

<p>For completeness, the <em>discrepancy</em> 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$.</p>

CC BY-SA 3.0
2013-10-14T15:10:21.527Z
I added absolute values to make sure this is the standard definition of discrepancy, let me know if you meant something else.
Sasho Nikolov
<co.combinatorics>
Colouring achieving simple discrepancy bound?
András Salamon
# Colouring achieving simple discrepancy bound?

(Asked by: username_0 on 2013-10-14)

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](https://en.wikipedia.org/wiki/Chernoff_bound) using the [probabilistic method](https://en.wikipedia.org/wiki/Probabilistic_method) (for instance, see the outline proof at the [Wikipedia article on discrepancy](https://en.wikipedia.org/wiki/Discrepancy_of_hypergraphs)).

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

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: I added absolute values to make sure this is the standard definition of discrepancy, let me know if you meant something else.  

---

## 2 answers

### Answer by username_1 on 2013-10-14. Score: 7 | Accepted answer

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](http://link.springer.com/chapter/10.1007/978-3-642-23719-5_35) 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](http://www.cs.princeton.edu/~chazelle/book.html).

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 by username_2 on 2019-09-20. Score: 0

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.


---

