# The minimum size of Max-Cut for graphs of half density

As discussed in the following math overflow question, Max cut value in a random graph, the max-cut of a random graph $G(n,1/2)$ is $\frac{n^2}{8} + \Theta(n^{3/2})$ with high probability.

My question is this: Does there exist a family of graphs with relative density about $\frac{1}{2}$ with max-cut size being $\frac{n^2}{8}+ o(n^{3/2})$? If not, can we show that every graph with $\frac{1}{2}$ relative density has a cut of size $\frac{n^2}{8} + \Omega(n^{3/2})$ ?

(It is possible that any of the well-known explicit pseudorandom graphs with $\frac{1}{2}$ relative density,such as Paley graphs and etc, will satisfy this property but I haven't been able to verify whether this is the case or not by looking at a few survey papers.)

-

Let $n=4k$, and let $G$ be a graph consisting of two disjoint copies of $K_{2k}$ along with $k$ additional edges (the $k$ additional edges being there to give $G$ density $1/2$).
Any cut of $G$ cuts at most $k^2$ edges from each of the complete graphs, along with the $n$ additional edges, so the max-cut value is at most $2k^2+k=n^2/8+n/4$.
Thanks! I don't know how I didn't see that myself! But for the application that I had in mind what is really necessary is that a graph $G=(V,E)$ such that for any $S\subset V$ we have $|E(S,S^c)-\frac{|S||S^c|}{2}|\leq o(n^{3/2})$. Maybe I ask about the existence of such graphs in another question. – Nick B. Dec 4 '12 at 3:01