7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

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

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.