# Random graphs

Ken Clarkson bugged me on a recent post here about why Wikipedia had no article on Edgar Gilbert (obviously, they do now) which is why I've become sensitive to the following issue:

I saw a talk today (on key distribution in computer security) that invoked the Erdős–Rényi model for random graphs. Not much of a surprise there: it's a very standard model. Except that it wasn't the Erdős–Rényi \( G(n,M) \) model (the one in which one chooses uniformly among graphs with a fixed number of edges), it was Gilbert's \( G(n,p) \) model in which each edge is chosen to be included or not, independently of the other edges, with a given probability. Why does Gilbert get so little credit for this? I can understand the reasons for conflating the \( G(n,M) \) and \( G(n,p) \) models but shouldn't it at least be the Erdős–Rényi–Gilbert model?

### Comments:

**ext_353166**:

**2011-03-05T02:46:22Z**

Stigler's Law of Eponymy.

**arvindn**:

**2011-03-06T00:54:15Z**

Yeah, especially considering that "Erdős–Rényi–Gilbert model" just rolls off the tongue ;-)

**11011110**:

**2011-03-06T01:01:13Z**

Well, there is that, but leaving Gilbert off doesn't make it much more euphonic. A bigger problem with calling it the ""Erdős–Rényi–Gilbert model" is that the ERG Model is a different kind of random graph (it stands for Exponential Random Graph).

**ext_453792**: ERG vs ERG

**2011-03-07T19:35:07Z**

The fact that ERG is taken is a little problem, but we could call it the GER model if we needed to.

Bollobas's book _Random Graphs_ has probably been very influential in the ER moniker. From page xii of the preface: "Occasionally all these authors are credited with the foundation of the theory of random graphs. However, this is to misconceive the nature of the subject. Only Erdős and Rényi introduced the methods which underlie the probabilistic treatment of random graphs. The other authors were all concerned with enumeration problems and their techniques were essentially deterministic."

**11011110**: Re: ERG vs ERG

**2011-03-08T03:51:42Z**

Gilbert's paper is online, so you can see for yourself that Bollobas is grossly mischaracterizing his work. It's explicitly about random graphs (in the title!), it introduces the \( G(n,p) \) model, and it calculates the probability that a graph generated in this way is connected.

Gilbert appears to have done a little work on combinatorial enumeration problems (involving neclackes) but much more of his work was probabilistic in nature.