Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider two Erdos-Renyi random graphs $G_1, G_2$ on $n$ nodes, with the edges in each graph generated independently at random with probability $1/2$. My question is about the cut-distance between these two graphs. Recall that the cut-distance is the maximum over all cuts of the difference between the cut values of the two graphs. Using a standard Chernoff bound argument for each cut, followed by a union bound to maximize over all cuts, I get that the cut-distance between $G_1,G_2$ is $O(n^{3/2})$ with large probability. Is this the tightest bound one can show? I'm wondering if it is possible to get this distance down to $O(n)$?

share|cite|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.