2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nick B.
    Dec 4, 2012 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.