Question

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)$?

Answer 1

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