Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says

"There exists $a$ edges such that if they are removed, nodes $1$ and $2$ get disconnected with high probability (as $n\rightarrow \infty$), i.e., there are no paths left between nodes $1$ and $2$".

for cases $c=\ln n, (\ln n)^2$. In particular, I am interested in the least possible value (or scaling) of $a$.

For example, one way of disconnecting nodes $1$ and $2$ is to isolate node $1$ from its neighbors. Since $c>1$, the maximum degree of node $1$ is bounded above by $2\ln n/\ln\ln n$ with high probability as $n\rightarrow \infty$ (this is a known result). So, we can say that the minimum value of $a$ is less than $2\ln n/\ln\ln n$ or it scales as $O(\ln n/\ln\ln n)$.

  • 1
    $\begingroup$ I'm not sure if you have "with high probability" in the right place. You want that the disconnecting edges exist with high probability, not that 1 and 2 are disconnected with high probability, right? $\endgroup$ – Brendan McKay May 21 '13 at 14:16
  • $\begingroup$ You seem to be saying that if $c = \ln n$, then the maximum degree is going to be at most $2 \ln n / \ln \ln n$. I guess that's not the case? $\endgroup$ – Andrew D. King May 21 '13 at 15:35
  • $\begingroup$ There is more than one thing wrong with that statement about the degree of node $1$. It's conceivable that the mean would be higher than a high probability bound, but not here. I think that is a highly garbled version of the maximum of $n$ IID normals being about $c \log \log n$ standard deviations above the mean, though I think the standard deviation is $\sqrt{\log n}$ (as Poisson dist.). Second, why would you be looking at the maximum degree of a vertex of the graph, instead of just the greater of the degrees of nodes $1$ and $2$? So you can drop the $\log \log n$. $\endgroup$ – Douglas Zare May 21 '13 at 21:50
  • $\begingroup$ I think the maximum degree is a red herring. For example, when $c<1$ is constant you can easily check that the probability of having two edge-disjoint paths from 1 to 2 goes to zero, whereas the probability of one of them having degree 0 or 1 does not go to 1. So with high probability they can be separated by removing one edge even though there is some non-zero probability both have degree 2. The same holds for $c=1$, but larger $c$ is harder. I'm pretty sure this has all been worked out, but I'm too lazy to search. $\endgroup$ – Brendan McKay May 22 '13 at 2:30
  • 1
    $\begingroup$ I don't think the degree is a red herring. I think for large $c$, the easiest way to disconnect $1$ from $2$ is likely to be by eliminating all of the edges around $1$ or around $2$. $\endgroup$ – Douglas Zare May 22 '13 at 3:47

The thing you're looking for is the size of the minimum cut in an Erdos-Renyi graph. (Actually, to be more accurate, you're looking for the size of the minimum such cut that separates vertices 1 and 2.) There's ample literature on minimum cuts in random graphs, and I'm sure you can find the answer there.

I'd try to figure out the answer myself, but it's not clear what you're actually asking about. Are you looking for the expected size of the cut? Or for an almost-sure size of a cut? Part of the issue is that your math seems wrong. The maximum degree of node 1 is actually bounded above by any superconstant function w.h.p. as n tends to infinity.

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