# Combinatorial discrepancy of the system of all cuts

This is a variant of this previous question. 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. But maybe one can do better by exploiting the cut structure.

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

• 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 Jul 26 '15 at 19:22
• @domotorp I think you are right! – Sasho Nikolov Jul 26 '15 at 20:01