6
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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.

EDIT

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.

$\endgroup$
4
  • $\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, 2011 at 19:49
  • $\begingroup$ See the reference in the edit. $\endgroup$
    – Igor Rivin
    Jan 26, 2011 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$ Jan 26, 2011 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, 2017 at 13:13
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Didn't see Igor's second post there... $\endgroup$ Jan 26, 2011 at 20:06

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.