0
$\begingroup$

I am interested to find out what’s the probability that an Erdos-Renyi graph $\mathcal{G}(n,p)$ is a regular graph?

I believe this is a really hard question whose non-asymptotic results are probably impossible to find. Therefore, I would probably settle for any asymptotic large deviation result or may be some upper bound of the probability.

I think there is no closed form of joint degree distribution of Erdos Renyi graph, which makes this a hard problem.

Any result in this direction will be very much appreciated.

$\endgroup$
1
$\begingroup$

I don't think this counts as a full answer but I believe it is too long for the comments. It may give insight on how to approach this

  1. Let $G$ and $G'$ be two labelled graphs on $\{1,\ldots, n\}$ [i.e., $G=G'$ iff $ij \in E(G)$ implies $ij \in E(G')$ and vice versa mere isomorphism doesn't count] with the same number $m$ of edges. If a graph is drawn according to ER$(n,p)$, the $G$ and $G'$ have the same probability $P_n(m,p)$ of being chosen (which is a function of $n,p$ and $m=|E(G)| = |E(G')|$). This I know can be calculated explicitly.

  2. There is a formula (I think) that approximates the number $N(k)$ of $k$-regular graphs on $\{1,\ldots, n\}$.

So the probability $P$ of chossing a $k$-regular graph if drawing according to ER$(n,p)$ would come to

$$P= \sum_{k=1}^{n-1} N(k)P_n\left(\frac{kn}{2},p\right)$$

$\endgroup$

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.