Question

As discussed in the following math overflow question, http://mathoverflow.net/questions/53389/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.)

Answer 1

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