Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is exactly $s$ (hence the number of $−1$s is $n−s$.) Given a configuration $\sigma$, we look at each node $i$ and sum the values assigned to its neighbors, call this $\xi_i(\sigma)$. We then count the number of nodes for which $\xi_i(\sigma)$ is nonnegative: $$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$$ The question is: what is the configuration $\sigma$ that maximizes $N(\sigma)$? More importantly, can we give a bound on $(\max N)/n$ in terms of $s/n$. I am wondering if this problem looks familiar to anyone, or if it can be reduced to some known problem in graph theory. If it helps, the graph can be assumed to be random of Erdős-Renyi type (say, G(n,p) with edge probability $p ~ (\log n)/n$, i.e. average degree growing as $\log n$). The main instrest is in the case where $s/n \in (0,1/2)$.

  • 1
    $\begingroup$ I changed the title, because what you're asking is related to discrepancy problems in range spaces. It's NOT however related to discrepancy in graphs (which is more about edge density deviations) $\endgroup$ May 14, 2012 at 16:45
  • 2
    $\begingroup$ simple bound: take $\sigma$ at random; $\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$, where $\delta_i$ is the degree of vertex $i$ and $C$ is some constant. So, $E[N(\sigma)] \geq \sum_i{1-\exp(-C\delta_i (s/n - 1/2)^2)}$. If say $s = 3n/4$ and the graph is $(16/C)\log n$-regular, then there exists $\sigma$ such that $N(\sigma) \geq n - O(1)$. $\endgroup$ May 14, 2012 at 17:06
  • $\begingroup$ @Suresh: Thanks. That is what I like about asking computer scientists, you learn something new! So where is good place to learn about discrepancy problems in the range space? (Maybe a short concise paper?) $\endgroup$
    – passerby51
    May 14, 2012 at 19:28
  • 1
    $\begingroup$ @Sasho: Thanks. For some reason, I can't see the equations properly (they have collided with the surrounding text.) I will try to read it and get back to you. But I should mention that the interesting regime for me is $s/n \in (0,1/2)$ and the problem seems to get harder as $s/n$ approaches $1/2$. (This is due to symmetry consideration in the original problem where this came from.) I don't think looking at a random $\sigma$ would do it for $s/n \in (0,1/2)$. $\endgroup$
    – passerby51
    May 14, 2012 at 19:39
  • $\begingroup$ The guess/hope is that $(\max N)/n = o(1)$ for say G(n,p) with $p ~ (\log n) / n$ or $p ~ (\log n)^{1+\epsilon} /n$ . I just realized the typo in my original post regarding $p$. Sorry about that. The avarage degree is growing as $\log n$ not $p$. $\endgroup$
    – passerby51
    May 14, 2012 at 19:40

2 Answers 2


You could approach this with a "second moment method" calculation, similar to the one I used in A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.

When the average degree grows like a sufficiently large constant times $\log n$, this approach has often been sufficient to find precisely the threshold of satisfiability. It could possibly also show the fraction of clauses that can be satisfied in an unsatisfiable instance, although I have not investigated that.

To make your problem look more like my general one, you can view it as a "MAX-AT-LEAST-HALF-SAT" with a special graphical structure underlying the clauses in the CNF formula. I don't think that this special structure will help in a worst-case analysis, however, and since your clause size is non-uniform and your "bad" assignment set is growinyou'll have to go through the calculation and see if it still works.

  • $\begingroup$ looking at this as a CSP seems indeed a better fit than looking at it as a discrepancy problem $\endgroup$ May 15, 2012 at 12:47
  • $\begingroup$ Thank you. This looks very interesting. I will look into it. $\endgroup$
    – passerby51
    May 15, 2012 at 22:55

Let me elaborate on my comment. First, this is similar to discrepancy, but of course different in several ways. Given a system of $m$ sets $S_1, \ldots, S_m \subseteq \{1, \ldots n\} = [n]$, the discrepancy of the system is $\min_{\sigma:[n] \rightarrow \{\pm 1\}}{\max_{j}{|\sum_{i \in S_j}{\sigma(i)}|}}$. Let's denote $\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$. Your definition differs in that you want to know for how many sets $\sigma(S_j)$ is positive and discrepancy asks how big is $\sigma(S_j)$ in magnitude in the worst case. For a quick intro, maybe my scribe notes can help. Chazelle has a nice book that goes into a lot of detail.

For an easy probabilistic lower bound when $s > n/2$, as in my comment, given a graph $G = ([n], E)$ with degree sequence $\delta_1, \ldots, \delta_n$, you can pick $\sigma$ uniformly at random from all sequences with $s$ $1$'s (the $\sigma_i$ are not independent, but it should be possible to prove a Chernoff bound in this case too). We have $E[\xi_i(\sigma)] = \delta_i s/n$ and, by a Chernoff bound, $\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$ for some constant $C$. So $E[N(\sigma)] \geq n - \sum_i{\exp(-C\delta_i (s/n - 1/2)^2)}$. So there exists some $\sigma$ that achieves this bound.

EDIT: Seems that you are interested in the case $s < n/2$. Let's pick $\sigma$ at random in the same way as in the previous paragraph. Using a version of the central limit theorem for sampling without replacement ($\sigma$ is a sample of size $s$ without replacement from the vertices of the graph), you should be able to show that $\xi_i(\sigma)$ behaves like a Gaussian with mean $\delta_i (2s/n - 1)$ and variance about $\delta_i$, so $\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$ for some C and $\eta(n)$ an error parameter from the central limit theorem. We should have $n\eta(n) = o(n)$, so you can take $N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$.

Disclaimers: this is only meaningful if $\delta_i$ are constant/small or $s/n$ is very close to $n/2$. Also the calculations are somewhat heuristic and not very carefully done.

  • $\begingroup$ Thank you for the nice links and the argument. I like the probabilistic argument, but I think there is something wrong with your bound. You can see this, by setting $s = 0$, for which we should have $Pr[\xi_i(\sigma) < 0] = 1$. It seems that this is what went wrong: If you pick $\sigma$ uniformly at random from the set specified in the problem, each $\sigma_j$ has prob. $\gamma := s/n$ of being $+1$ and prob. of $1-\gamma$ of being $-1$. Hence, $E[ \xi_i(\sigma)] = (2\gamma-1) \delta_i$ which is negative for $\gamma \in (0,1/2)$ ... $\endgroup$
    – passerby51
    May 15, 2012 at 23:00
  • $\begingroup$ The $\{\sigma_j\}$ will not be independent and strictly speaking we can not use say Hoeffding inequality. But let us ignore this minor detail and assume them i.i.d. Then, the bound would be $Pr[ \frac{1}{\delta_i} \xi_i(\sigma) < -t + 2\gamma - 1) \le \exp ( -\delta_i t^2/2)$ which holds for $ t \ge 0$. We can not set $t = 2\gamma - 1 < 0$ to get $Pr[\xi_i(\sigma) <0]$. $\endgroup$
    – passerby51
    May 15, 2012 at 23:03
  • $\begingroup$ sorry, i should've specified that: the assumption here was that $s > n/2$. otherwise this makes no sense and you need something stronger like Berry-Esseen. i think the $\sigma_j$ can be assumed to be essentially independent $\endgroup$ May 15, 2012 at 23:07
  • $\begingroup$ @passerby51 added a sketch how you might attempt to use a quantitative version of the central limit theorem to extend the probabilistic bound to $s/n < 1/2$. $\endgroup$ May 15, 2012 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.