<p>You could approach this with a "second moment method" calculation, similar to the one I used in <a href="http://www.math.cmu.edu/~adf/research/genksat.pdf">A sharp threshold for a random constraint satisfaction problem</a>, <em>Discrete Mathematics</em> 285/1-3 (2004), 301-305.</p>

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

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

CC BY-SA 3.0
2012-05-15T12:47:49.827Z
looking at this as a CSP seems indeed a better fit than looking at it as a discrepancy problem
Sasho Nikolov
CC BY-SA 3.0
2012-05-15T22:55:29.093Z
Thank you. This looks very interesting. I will look into it.
passerby51
CC BY-SA 3.0
2012-05-14T20:27:03.313Z
2012-05-14T20:27:03.313Z
Abraham D Flaxman
<p>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 <a href="http://paul.rutgers.edu/~anikolov/Files/Discrepancy.pdf" rel="nofollow">scribe notes</a> can help. Chazelle has a nice <a href="http://www.cs.princeton.edu/~chazelle/pubs/book.pdf" rel="nofollow">book</a> that goes into a lot of detail.</p>

<p>For an easy probabilistic lower bound when $s &gt; 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) &lt; 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. </p>

<p>EDIT: Seems that you are interested in the case $s &lt; 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)$.</p>

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

CC BY-SA 3.0
2012-05-15T23:00:18.337Z
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)$ ...
passerby51
CC BY-SA 3.0
2012-05-15T23:03:57.990Z
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]$.
passerby51
CC BY-SA 3.0
2012-05-15T23:07:32.790Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-05-15T23:33:07.687Z
@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$.
Sasho Nikolov
CC BY-SA 3.0
2012-05-14T20:38:57.847Z
2012-05-15T23:31:04.803Z
2012-05-15T23:31:04.803Z
Sasho Nikolov
<p>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)$.</p>

CC BY-SA 3.0
2012-05-14T16:45:11.117Z
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)
Suresh Venkat
CC BY-SA 3.0
2012-05-14T17:06:34.633Z
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)$.
Sasho Nikolov
CC BY-SA 3.0
2012-05-14T19:28:21.560Z
@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?)
passerby51
CC BY-SA 3.0
2012-05-14T19:39:52.357Z
@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)$.
passerby51
CC BY-SA 3.0
2012-05-14T19:40:14.650Z
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$.
passerby51
<graph-theory><co.combinatorics><optimization>
A variation on discrepancy involving random graphs
passerby51
# A variation on discrepancy involving random graphs

(Asked by: username_0 on 2012-05-14)

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

**Tags:** graph-theory, co.combinatorics, optimization
> **Comments:**
> **username_1**: 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)  
> **username_2**: 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)$.  
> **username_0**: @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?)  
> **username_0**: @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)$.  
> **username_0**: 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$.  

---

## 2 answers

### Answer by username_3 on 2012-05-14. Score: 8

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](http://www.math.cmu.edu/~adf/research/genksat.pdf), *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.

> **Comments:**
> **username_2**: looking at this as a CSP seems indeed a better fit than looking at it as a discrepancy problem  
> **username_0**: Thank you. This looks very interesting. I will look into it.  

---

### Answer by username_2 on 2012-05-14. Score: 3

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](http://paul.rutgers.edu/~anikolov/Files/Discrepancy.pdf) can help. Chazelle has a nice [book](http://www.cs.princeton.edu/~chazelle/pubs/book.pdf) 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.

> **Comments:**
> **username_0**: 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)$ ...  
> **username_0**: 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]$.  
> **username_2**: 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  
> **username_2**: @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$.  

---

