<p>I doubt you can do better than $O(n^{3/2})$. Here is a lower bound, using old arguments by Spencer and Erdos, that shows that the discrepancy is $\Omega(n^{3/2})$ if you expand the set system to cuts of induced subgraphs. <em>See the edit for a lower bound for cuts as well, suggested by Domotor.</em></p>

<p>Let $V$ be the vertex set of the complete graph, and fix a function $f:{V \choose 2} \to \{-1, 1\}$. Split $V$ into $L$ and $R$, each of equal size. Let $S$ be a random subset of $L$. Then, for any $v \in R$, 
$$
\mathbb{P}\left(\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}\right) \ge 1/4,
$$
for a suitable constant $c$. (This can be proved using the Central Limit Theorem or a 4-th moment argument.) Letting $T_0$ be the subset of all $v \in R$ satisfying $\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}$, we have that $\mathbb{E}|T_0| \geq n/8$. So there exists some choice of $S$ such that $T_0$ has size at least $n/8$: fix such an $S$ and pick $T = \{v \in R: \sum_{u \in S}{f(u, v)} \geq c\sqrt{n}\}$ or $T = \{v \in R: \sum_{u \in S}{f(u, v)}\leq -c\sqrt{n}\}$, whichever is larger. Clearly 
$$
\Bigl|\sum_{u \in S, v \in T}{f(u,v)}\Bigr| \ge \frac{cn^{3/2}}{16}.
$$</p>

<p><strong>EDIT</strong>: As Domotor pointed out in a comment the above suffices for a $\Omega(n^{3/2})$ lower bound on the discrepancy of cuts as well. Let $S$ and $T$ be the sets above, and $U = V \setminus (S \cup T)$. Define $f(X,Y) = \sum_{x \in X, y \in Y}{f(x,y)}$ for any two subsets $X,Y\subseteq V$. Assume without loss of generality that $f(S,T) \ge c'n^{3/2}$ for $c' = c/16$ (the case $f(S,T) \le -c'n^{3/2}$ is analogous). Then at least one of the cases below holds:</p>

<ul>
<li>$f(S,U) \ge -c'n^{3/2}/2$ and $f(S, T \cup U) \ge c'n^{3/2}/2$; </li>
<li>$f(T,U) \ge -c'n^{3/2}/2$ and $f(S\cup U, T) \ge c'n^{3/2}/2$;</li>
<li>$f(S \cup T, U) = f(S, U) + f(T,U) &lt; -c'n^{3/2}$.</li>
</ul>

<p>In each case the discrepancy of some cut is $\Omega(n^{3/2})$.</p>

CC BY-SA 3.0
2015-07-26T19:22:34.597Z
Don't we always get the general case from here? I mean suppose we already have an $S$ and $T$ such that $f(S,T)=N$ (you know what this means) and denote by $U$ the remaining vertices. If $f(S,U)\ge -N/2$, then the partition is $(S, T\cup U)$. If $f(T,U)\ge -N/2$, then the partition is $(S\cup U, T)$. Finally, if $f(S,U)\le -N/2$ and $f(T,U)\le -N/2$, then the partition is $(S\cup T, U)$.
domotorp
CC BY-SA 3.0
2015-07-26T20:01:39.367Z
@domotorp I think you are right!
Sasho Nikolov
CC BY-SA 3.0
2015-07-26T05:41:52.883Z
2015-07-26T21:03:11.877Z
2015-07-26T21:03:11.877Z
Sasho Nikolov
<p>This is a variant of <a href="https://cstheory.stackexchange.com/q/25974/15637">this previous question</a>. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More precisely, my ground set $X$ is the set of all 2-element subsets of $[n]=\{1,\ldots,n\}$, and I am looking at the set system which consists of the sets $S_U=\{\{i,j\}\in X\ :\ i\in U\text{ and }j\not\in U\}$ for all $U\subseteq[n]$. Is there a function $f:X\to\{1,-1\}$ such that</p>

<p>$$\forall U\subseteq[n]\ \left\lvert\sum_{\{i,j\}\in S_U}f(\{i,j\})\right\rvert=O(n)\,?$$</p>

<p>Choosing $f$ at random gives $O(n^{3/2})$ and I think that is also what follows from Spencer's <a href="http://www.ams.org/journals/tran/1985-289-02/S0002-9947-1985-0784009-0/" rel="nofollow noreferrer">6 standard deviations theorem</a>. But maybe one can do better by exploiting the cut structure.</p>

<graph-theory><co.combinatorics>
Combinatorial discrepancy of the system of all cuts
Thomas Kalinowski
# Combinatorial discrepancy of the system of all cuts

(Asked by: username_0 on 2015-07-24)

This is a variant of [this previous question](https://cstheory.stackexchange.com/q/25974/15637). In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More precisely, my ground set $X$ is the set of all 2-element subsets of $[n]=\{1,\ldots,n\}$, and I am looking at the set system which consists of the sets $S\_U=\{\{i,j\}\in X\ :\ i\in U\text{ and }j\not\in U\}$ for all $U\subseteq[n]$. Is there a function $f:X\to\{1,-1\}$ such that

$$\forall U\subseteq[n]\ \left\lvert\sum\_{\{i,j\}\in S\_U}f(\{i,j\})\right\rvert=O(n)\,?$$

Choosing $f$ at random gives $O(n^{3/2})$ and I think that is also what follows from Spencer's [6 standard deviations theorem](http://www.ams.org/journals/tran/1985-289-02/S0002-9947-1985-0784009-0/). But maybe one can do better by exploiting the cut structure.

**Tags:** graph-theory, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2015-07-26. Score: 7 | Accepted answer

I doubt you can do better than $O(n^{3/2})$. Here is a lower bound, using old arguments by Spencer and Erdos, that shows that the discrepancy is $\Omega(n^{3/2})$ if you expand the set system to cuts of induced subgraphs. *See the edit for a lower bound for cuts as well, suggested by Domotor.*

Let $V$ be the vertex set of the complete graph, and fix a function $f:{V \choose 2} \to \{-1, 1\}$. Split $V$ into $L$ and $R$, each of equal size. Let $S$ be a random subset of $L$. Then, for any $v \in R$,
$$
\mathbb{P}\left(\Bigl|\sum\_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}\right) \ge 1/4,
$$
for a suitable constant $c$. (This can be proved using the Central Limit Theorem or a 4-th moment argument.) Letting $T\_0$ be the subset of all $v \in R$ satisfying $\Bigl|\sum\_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}$, we have that $\mathbb{E}|T\_0| \geq n/8$. So there exists some choice of $S$ such that $T\_0$ has size at least $n/8$: fix such an $S$ and pick $T = \{v \in R: \sum\_{u \in S}{f(u, v)} \geq c\sqrt{n}\}$ or $T = \{v \in R: \sum\_{u \in S}{f(u, v)}\leq -c\sqrt{n}\}$, whichever is larger. Clearly
$$
\Bigl|\sum\_{u \in S, v \in T}{f(u,v)}\Bigr| \ge \frac{cn^{3/2}}{16}.
$$

**EDIT**: As Domotor pointed out in a comment the above suffices for a $\Omega(n^{3/2})$ lower bound on the discrepancy of cuts as well. Let $S$ and $T$ be the sets above, and $U = V \setminus (S \cup T)$. Define $f(X,Y) = \sum\_{x \in X, y \in Y}{f(x,y)}$ for any two subsets $X,Y\subseteq V$. Assume without loss of generality that $f(S,T) \ge c'n^{3/2}$ for $c' = c/16$ (the case $f(S,T) \le -c'n^{3/2}$ is analogous). Then at least one of the cases below holds:

* $f(S,U) \ge -c'n^{3/2}/2$ and $f(S, T \cup U) \ge c'n^{3/2}/2$;
* $f(T,U) \ge -c'n^{3/2}/2$ and $f(S\cup U, T) \ge c'n^{3/2}/2$;
* $f(S \cup T, U) = f(S, U) + f(T,U) < -c'n^{3/2}$.

In each case the discrepancy of some cut is $\Omega(n^{3/2})$.

> **Comments:**
> **username_2**: Don't we always get the general case from here? I mean suppose we already have an $S$ and $T$ such that $f(S,T)=N$ (you know what this means) and denote by $U$ the remaining vertices. If $f(S,U)\ge -N/2$, then the partition is $(S, T\cup U)$. If $f(T,U)\ge -N/2$, then the partition is $(S\cup U, T)$. Finally, if $f(S,U)\le -N/2$ and $f(T,U)\le -N/2$, then the partition is $(S\cup T, U)$.  
> **username_1**: @username_2 I think you are right!  

---

