Help with proof that a binomial random graph with m edges is equally likely to be any uniform random graph with m edges

74 Views Asked by At

I'm currently working through Introduction to Random Graphs by Frieze & Karonski, and I'm struggling with some of the notation (and quite possibly some background concepts) in a lemma.

Please note that I'm quite the newcomer to mathematics. I kindly ask you to err on the side of over-explaining, as I have very little background in the field. (I'm working on it!)

Context

The book begins by presenting two models of random graphs.

The first is called uniform random graph, and it models random graphs as the set of all graphs with $n$ vertices and $m$ edges. It is denoted by $\mathbb G{_n}{_,}{_m} = ([n], E{_n}{_,}{_m})$. It's probability is assigned by: $$\mathbb P(G) = \binom{\binom n 2}{m}^{{^-}{^1}}$$

The second is called binomial random graph, and it models random graphs as a set of $n$ vertices with a probability $p$ of an edge existing for each vertex pair. It is denoted by $\mathbb G{_n}{_,}{_p} = ([n], E{_n}{_,}{_p})$. It's probability is assigned by: $$\mathbb P(G) = p^m(1-p)^{{^\binom n 2}{^-}{^m}}$$

Question

Lemma: A random graph $G{_n}{_,}{_p}$ given that its number of edges is $m$, is equally likely to be one of the $\binom{\binom n 2}{m}$ graphs that have $m$ edges.

The book offers the following proof, which I'm having trouble understanding:

proof of lemma 1.1

Question 1: What allows us to write the first line of the proof? It's not obvious to me that

$${\mathbb P}(\mathbb G{_n}{_,}{_p} = G_0 | |E{_n}{_,}{_p}| = m) = \frac{\mathbb {P}(\mathbb G{_n}{_,}{_p} = G_0 , |E{_n}{_,}{_p}| = m)}{\mathbb {P}(| E{_n}{_,}{_p}| = m)}$$.

Is this Bayes theorem in disguise?

Subquestion: how do I read the numerator? Specifically, what does the comma designate?