# Random graph terminology. Math geeks, please. **URL:** \ **Category:** Factual Questions\ **Created:** [July 7, 2003, 4:37pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798 "2003-07-07T16:37:34Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [July 7, 2003, 4:37pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/1 "2003-07-07T16:37:34Z")
Ok, Erdos’ original use of the probablistic method for graphs uses G(n,p=.5) where G has n vertices and any two are adjacent with probability .5. When this is generalized to G(n,p), is this called an Erdos-Szerkes random graph? Is there terminology for this basic class of random graphs? ---
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [July 7, 2003, 4:51pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/2 "2003-07-07T16:51:21Z")
Oops! Wrong forum. Mods please? To GQ? ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [July 7, 2003, 6:04pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/3 "2003-07-07T18:04:09Z")
Off to GQ. **DrMatrix** - Moderator ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 7, 2003, 9:16pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/4 "2003-07-07T21:16:31Z")
Paging **rtfirefly** … ---
**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\ **Post date:** [July 7, 2003, 9:42pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/5 "2003-07-07T21:42:05Z")
Just saw this, but have to head home. Later… ---
**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\ **Post date:** [July 7, 2003, 11:13pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/6 "2003-07-07T23:13:04Z")
I think that’s the **Erdös-Rényi** random graph G(n,p). See [here](http://math.ucsd.edu/~vanvu/papers/random.html), for instance. In general, Erdös’ name seems to be linked with Rényi’s in the random-graph literature; at least, that’s what turns up when I Google “random graph” together with “Erdös”. The [Erdös-Szekeres Theorem](http://mathworld.wolfram.com/Erdos-SzekeresTheorem.html), which you may have gotten names confused with, is something different, although they seem to have sprung from the same root, in a way. ---
**Author:** ![Digital\_Stimulus](https://avatars.discourse-cdn.com/v4/letter/d/aeb1de/32.png) [@Digital\_Stimulus](https://boards.straightdope.com/u/Digital_Stimulus)\ **Post date:** [July 7, 2003, 11:19pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/7 "2003-07-07T23:19:50Z")
> [@](#): > > \*Originally posted by RTFirefly \* > **I think that’s the Erdös-Rényi random graph G(n,p).** Exactly right. There’s some neat research going on right now by Barabasi (for instance, see [http://www.science.nd.edu/physics/Faculty/barabasi.html](http://www.science.nd.edu/physics/Faculty/barabasi.html) and [http://human-nature.com/nibbs/02/linked.html](http://human-nature.com/nibbs/02/linked.html)), not to mention Watts (see [http://pup.princeton.edu/titles/6768.html](http://pup.princeton.edu/titles/6768.html) and [http://smallworld.sociology.columbia.edu/watts.html](http://smallworld.sociology.columbia.edu/watts.html)). I’d recommend Barabasi’s book Linked for an interesting and accessible read (though light on actual graph theory). Kramer ---
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [July 8, 2003, 5:30pm UTC](https://boards.straightdope.com/t/random-graph-terminology-math-geeks-please/186798/8 "2003-07-08T17:30:22Z")
Woah man. I’m reading a paper of Barabasi’s on scale-free graphs right now (not a huge coincidence). Thanks, guys. Erd"os-R’enyi is exactly right. Now, how the hell do you do accents? The Erdos-Szerkes Theorem is one of those things that needn’t really a namesake, like De Morgan’s Laws and crap like that. I’ll have to smack my supervisor for calling them Erdos-Szerkes.