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?
Oops! Wrong forum. Mods please? To GQ?
Off to GQ.
DrMatrix - Moderator
Paging rtfirefly…
Just saw this, but have to head home. Later…
I think that’s the Erdös-Rényi random graph G(n,p). See here, 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, which you may have gotten names confused with, is something different, although they seem to have sprung from the same root, in a way.
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 and http://human-nature.com/nibbs/02/linked.html), not to mention Watts (see http://pup.princeton.edu/titles/6768.html and 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
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.