6
$\begingroup$

Question.

Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence using the (classical) configuration model.

How to compute or precisely estimate the probability to obtain a simple graph (no loop, no multi-edge)?

For instance, if the sequence is $1, 1, 2, 2, 3, 3$ (thus $n=6$), then the probability experimentally seems close to $0.016$.

Remark.

Classical results (Erdös-Gallai and Havel-Hakimi) tell if a given sequence may lead to a simple graph (graphic sequences). Therefore, they tell (in linear time) if the probability under concern is non-zero.

Related work.

There are beautiful asymptotic results for the probability under concern, see in particular Janson papers and van der Hofstad book.

There are also beautiful results based on properties of the sequence, in particular for regular graphs (all $d_i$ are equal) and bounded sequences (the maximal $d_i$ is lower than a given bound). See in particular McKay and Wormald works.

These results hold for families of graphs and consider limits when $n$ grows to infinity, and/or families of sequences of which properties can be specified (like maximum degree bounded by a power of $n$).

Warning.

This is not the situation I face: I do have one specific sequence and want to estimate the probability that the configuration model gives a simple graph for this specific sequence.

Related questions.

Is there a way to compute this probability in linear time and space, with respect to $n$?

If, instead of just one sequence, I have two sequences of integers (of same sum) and sample bipartite multi-graphs with the configuration model, what is the probability to obtain a simple bipartite graph (no multi-edge)?

Improve this question
$\endgroup$
19
  • $\begingroup$ I wonder whether the probability is really well-defined without some knowledge as to the properties of your specific sequence? $\endgroup$
    – gmvh
    May 20, 2020 at 8:01
  • $\begingroup$ @gmvh I may better define it as the fraction of multi-graphs with this degree sequence that are simple. $\endgroup$
    – Matthieu Latapy
    May 20, 2020 at 8:33
  • $\begingroup$ I think that @gmvh is asking about realizable degrees sequences. For example a degree sequence 1,2 does not corresponds to any graph. So the fraction is not well-defined. $\endgroup$
    – kerzol
    May 20, 2020 at 10:09
  • $\begingroup$ Hi Matthieu! I'm not quite clear what you need. You say you want to estimate the probability, and you say $n$ is huge, and as you say there are asymptotic results - so presumably you are in some regime where you think these asymptotic results don't give a good estimate? Is your probability close to 0, or close to 1, or somewhere moderate in between? If the expected number of self-edges and multiple edges is small, a Poisson approximation is typically good. But if it's high, and you want a better estimate than "near 0", then different methods are needed. We may need more details.... $\endgroup$
    – James Martin
    May 20, 2020 at 12:58
  • 3
    $\begingroup$ Since the number of configurations is easy to compute, and each simple graph (with given degrees) corresponds to the same number of configurations, what you are asking for is just the number of simple graphs. I'm not aware of a fast way to bound that number rigorously. $\endgroup$
    – Brendan McKay
    May 21, 2020 at 0:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.