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, for example, $O(n)$?

  • 1
    $\begingroup$ It sounds as though $G_1$ and $G_2$ are labelled graphs, so that there is a distinguished bijection between the vertex sets. Is this what you have in mind? $\endgroup$ – Anthony Quas Oct 6 '12 at 8:21
  • $\begingroup$ I guess I had the labelled version in mind, but now that you mention it, the unlabelled version (where one optimizes the cut distance over all labellings) is also very interesting. No idea if the answer changes substantially. $\endgroup$ – Donald Oct 9 '12 at 21:08

(To answer Anthony, I'm taking the two graphs to be on the same vertex set.)

This is an argument, without details, that the answer is $\Omega(n^{3/2})$.

Generate the graphs two vertices at a time. As each pair of vertices is generated and their adjacencies with the previous vertices are chosen randomly, put one vertex on each side of the cut. Choose which vertex goes on which side so as to maximize the number of edges of $G_1$ crossing the cut minus the number of edges of $G_2$ crossing the cut.

Let $X_i$ be the number of edges of $G_1$ across the cut, minus the number of edges of $G_2$ across the cut, after $i$ pairs of vertices have been generated. The differences $X_{i+1}-X_i$ are independent and the expectation of $X_{i+1}-X_i$ is, I believe, $\Omega(i^{1/2})$ (maybe someone will prove this for us). So with high probability, using some standard concentration inequality, $X_{n/2} = \Omega(n^{3/2})$.

Probably the constant can be improved by generating one vertex at a time and deciding which side of the cut to put it. But then the differences are not independent so the analysis is trickier.

| cite | improve this answer | |

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.