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