The question is simply this: Does there exist a (family of) graph $G=(V,E)$ such that $\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}|\leq o(n^{3/2})$. Such graphs would be very psedorandom pseudorandom as the edge density of all their cuts would be extremely close to the expected value if we had picked each edge with probability a half.
Background: As discussed in the following Math-overflow question http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph, with high probability a random $G(n,\frac{1}{2})$ graph has a cut $(S,S^c)$ with more than $\frac{n^2}{8}+\Omega(n^{3/2})$ edges. This implies that the following max-deviation lower bound: For almost every $G=(V,E)$ we have,
$ \max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}| = \Omega(n^{3/2})$
This lower bound means that simply by taking a random graph you cannot solve the above problem.
It could be true that the above for amost every graph result actually holds for every graph and this quantity is always $\Omega(n^{3/2})$. A proof of this would be quite interesting and would give evidence to a conjecture that I have in mind.
