# Cut-distance between two Erdos-Renyi random graphs

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

-
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? – Anthony Quas Oct 6 '12 at 8:21
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. – Donald Oct 9 '12 at 21:08

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