Cut-distance between two Erdos-Renyi random graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:52:37Z http://mathoverflow.net/feeds/question/108933 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108933/cut-distance-between-two-erdos-renyi-random-graphs Cut-distance between two Erdos-Renyi random graphs Donald 2012-10-05T17:01:03Z 2012-10-08T12:58:15Z <p>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)\$?</p> http://mathoverflow.net/questions/108933/cut-distance-between-two-erdos-renyi-random-graphs/109144#109144 Answer by Brendan McKay for Cut-distance between two Erdos-Renyi random graphs Brendan McKay 2012-10-08T12:58:15Z 2012-10-08T12:58:15Z <p>(To answer Anthony, I'm taking the two graphs to be on the same vertex set.)</p> <p>This is an argument, without details, that the answer is \$\Omega(n^{3/2})\$.</p> <p>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.</p> <p>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})\$.</p> <p>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.</p>