1
$\begingroup$

What is known about the distribution of edge cuts in random graphs? E.g., in the following graph:

enter image description here

removing edge $a$ disconnects the graph; there is only one way to cut with one edge (producing two components). Removing any of the pairs: $(a,b)$, $(a,c)$, $(a,d)$, $(b,c)$, $(c,d)$, $(b,d)$, also disconnects the graph (producing two components). So there are six ways to cut with two edges. Removing any three edges (there are four ways to do so) disconnects the graph (now producing three components). Finally, removing all four edges can be done in one way (producing four components). In this case, the distribution of cuts is:

enter image description here

Actually, I'm interested in the distribution of edge cuts that produce exactly two components. But if that's too difficult, any number will also work for me. I'm interested in random graph with $200-2000$ vertices.

$\endgroup$
4
  • $\begingroup$ What is the notion of random graph underlying your Question? The usual constructions do not guarantee that we will get a connected graph, so the "distribution of edge cuts" is problematic for that reason. $\endgroup$
    – hardmath
    Mar 29, 2020 at 15:14
  • 1
    $\begingroup$ Good point. E.g. an Erdős–Rényi graph; or some other. $\endgroup$
    – corey979
    Mar 29, 2020 at 15:59
  • 1
    $\begingroup$ What edge probability are you interested in? $\endgroup$ Mar 29, 2020 at 16:06
  • $\begingroup$ To be honest, I'm not sure. I wish to compare this edge cut property with my actual graphs, in which I have $n=200-2000$ vertices, and $m\approx 5n$ edges. $\endgroup$
    – corey979
    Mar 29, 2020 at 16:21

1 Answer 1

2
$\begingroup$

Let's consider the random graph $\mathcal G_{n,m}$ with $n$ vertices and $m$ edges, and try to count the number of $k$-edge cuts.

If we pick a random $k$-edge set and delete it, what we're left with is the random graph $\mathcal G_{n,m-k}$, it's just chosen funny. We could compute the probability that $\mathcal G_{n,m-k}$ is connected, and that would tell us the fraction of the $\binom mk$ $k$-edge sets that are cuts. But I'm going to get there indirectly.

When we're trying to figure out when the random graph is connected, there are three regimes:

  • When the number of edges is too small, the graph is almost never connected. (So if $k$ is large, almost all $\binom mk$ sets of $k$ edges are cuts.)
  • When the number of edges is large enough, the graph is almost always connected. (We're not interested in this case.)
  • Around the boundary, whether the graph is connected or disconnected depends almost solely on whether there are isolated vertices.

This is a result usually proved in the limit as the number of vertices tends to $\infty$. But it's specifically true in your range of graphs with $n \in [200, 2000]$ vertices, if we start with about $5n$ edges and delete some. For example, experimentally:

  • When I took $1000$ random graphs with $200$ vertices and $1000$ edges, $995$ were connected and $5$ had an isolated vertex.
  • When I took $1000$ random graphs with $200$ vertices and $600$ edges, $635$ were connected, $363$ had one or more isolated vertices, and only $2$ had a component of order $2$.
  • When I took $1000$ random graphs with $2000$ vertices and $10000$ edges, $910$ were connected and $90$ had one or two isolated vertices.
  • When I took $1000$ random graphs with $2000$ vertices and $6000$ edges, only $3$ were connected, but only $34$ were disconnected for reasons other than having isolated vertices.

Anyway, this tells us that if we want to estimate the number of $k$-edge cuts in a random graph, we should count the number of $k$-edge sets that isolate a vertex. As a rough approximation, this is going to be $$ \sum_{i=1}^n \binom{m-d_i}{k-d_i} $$ where $d_1, d_2, \dots, d_n$ is the degree sequence of the graph. (But if you're using this as a base of comparison of your graphs with random graphs, you should also check if your degree sequence matches the degree sequence of a random graph with the same number of edges.)

The sum above is incorrect because it ignores overlap, but for small $k$, the overlap should be negligible, and for large $k$, almost all $k$-edge sets will be cuts.

In the middle range, the Poisson approximation is often used. (And actually, we can use it for any $k$.) To find the probability that a vertex in $\mathcal G_{n,m-k}$ is isolated, first approximate choosing $m-k$ edges exactly by choosing each edge independently with probability $p = (m-k)/\binom n2$. The probability that a vertex is isolated is $(1-p)^{n-1} \approx e^{-np}$, or $\exp(-\frac{2(m-k)}{n})$. So the expected number of isolated vertices is $n e^{-np}$. Call this quantity $\mu$. Then the Poisson approximation says that the probability of having no isolated vertices is about $e^{-\mu}$, which predicts that there are $(1 - e^{-\mu}) \binom mk$ $k$-edge cuts.

$\endgroup$
2
  • $\begingroup$ Cool answer. This is what I get when I plot $f(n,m,k) = \left( 1-\exp\left[ -n\exp \left(-\frac{n(m-k)}{n\choose 2}\right) \right] \right) {m\choose k}$ for $n=100$, $m=500$: imgur.com/vz2fHKi What do you think? $\endgroup$
    – corey979
    Mar 29, 2020 at 17:20
  • $\begingroup$ I haven't tried plotting it myself, but it's very plausible. The number of cuts is expected to blow up for two reasons: (1) the probability of a random graph being connected changes very quickly from $\approx 1$ to $\approx 0$ and (2) the total number of $k$-edge sets already grows very quickly. You might want to fiddle with the scale so that the plot of $\binom mk$ (the total number of $k$-edge sets) looks reasonable, to get a clearer picture. $\endgroup$ Mar 29, 2020 at 18:13

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.