Let $G = G(n, 1/2)$ be an Erdos-Renyi graph in which each edge $e = (u,v)$ is present in the graph independently with probability $1/2$. For a subset of the vertices $S$, the cut value $c(S)$ is equal to the number of edges $(u,v)$ such that $u \in S$ and $v \not \in S$.

Clearly for any particular cut $S$, the expected value of $c(S)$ is $E[c(S)] = |S|\cdot|\bar{S}|/2 \leq n^2/8$.

By a Chernoff bound, the probability that any particular cut exceeds its expectation by an additive factor of $O(tn)$ is exponentially decreasing in $t^2$. By taking $t = \sqrt{n}$ and taking a union bound over all $2^n$ possible cuts $S$, we can see that with high probability:

$$\max_S \ c(S) \leq E[c(S)] + O(n^{3/2}) \leq n^2/8 + O(n^{3/2})$$

This naive analysis seems loose. My question is, can the $O(n^{3/2})$ term be improved asymptotically, or is this actually tight?


This is addressed in:

An upper bound for the maximum cut mean value Alberto Bertoni, Paola Campadelli and Roberto Posenato

Their bound is the same as yours; more precisely, for a random graph with $n$ vertices and $x n$ edges, for sufficiently large $x,$ they claim the size of max cut divided by $x n$ is bounded above by

$$\frac12 + \frac1{\sqrt{x}} + \frac12 \frac{\log x}{x},$$

so I assume this is tight.


A matching lower bound is provided in MR2060633 (2005c:68088) Coppersmith, Don(1-IBM); Gamarnik, David(1-IBM); Hajiaghayi, Mohammad Taghi(1-MIT); Sorkin, Gregory B.(1-IBM) Random MAX SAT, random MAX CUT, and their phase transitions. (English summary) Random Structures Algorithms 24 (2004), no. 4, 502–545. 68Q25 (60C05 68T20 68W40 82B26 82B44)

See Theorem 20.

| cite | improve this answer | |
  • $\begingroup$ They don't seem to claim a lower bound, so I don't see any reason to think this is tight... $\endgroup$ – Aaron Jan 26 '11 at 19:49
  • $\begingroup$ See the reference in the edit. $\endgroup$ – Igor Rivin Jan 26 '11 at 19:58
  • 4
    $\begingroup$ Igor's reference is correct. It's worth elaborating since the proof is easy. Order the vertices uniformly at random. Build the cut one vertex at a time. For each vertex, put it on whichever side maximizes the increase in the cut size. On average, for vertex $i \leq n/2$, you will gain about $i/2 + \Theta(\sqrt(i))$ edges across the cut. For $i > n/2$, you gain about $(n-i)/2 + \Theta(\sqrt{n-i})$ edges. Overall, you expect to get order $n^{3/2}$ extra edges. $\endgroup$ – Louigi Addario-Berry Jan 26 '11 at 20:21
  • $\begingroup$ What about the expected value of $c(S)$? The OP thinks it is clear, I do not. $\endgroup$ – TheNotMe Oct 27 '17 at 13:13

Sounds pretty credible to me. I'm reminded of the Alon/Spencer/Erd"os book "The Probabilistic Method" where they're addressing the clique number of a random graph. Again it's easy to see the probability that a particular clique is present. They then work quite hard giving counting and independence estimates for different potential cliques. Your situation sounds very similar. My guess would be that enough of the cuts are independent enough for you to pretend that their cut values are independent. Then if each one (of the roughly balanced cuts) has value $n^2/8\pm N$ where $N$ is normal with mean 0 and variance $\approx n^2$, the max of $2^n$ of these should be determined by the value that the normal takes with probability $2^{-n}$, namely $\Theta(n^{3/2})$.

| cite | improve this answer | |
  • $\begingroup$ Didn't see Igor's second post there... $\endgroup$ – Anthony Quas Jan 26 '11 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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