A variation on discrepancy involving random graphs 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)$.
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.