Talk:Random graph
From Wikipedia, the free encyclopedia
I'm linking here from quantifier elimination, but there random graph seems to have somewhat different meaning: it's the graph which contains every finite graph as a subgraph or something like that. I would expect that there is a correlation between them, but these do not seem to be entirely identical notions. Anyone has insight into this? I hope to check this at some point. -- vkuncak
-
- Oh yes vkuncak: on the one hand *THE* random graph is certain specific (unique up to isomorphism) graph with an infinite number (more specifically
) of vertices, on the other hand (informally) *A* random graph is a graph generated by some random process. More formally, it is any graph when viewed as a point in some probability space... in this latter view it's more common to talk about *random graphs* in plural, like in "random graphs have diameter 2"... however, most specialist would say "almost every graph have diameter 2" instead.
- Oh yes vkuncak: on the one hand *THE* random graph is certain specific (unique up to isomorphism) graph with an infinite number (more specifically
-
- There is a very nice *equivalence* (so to speak, under certain restrictions) of both pictures, thanks to a marvelous theorem discovered independently by Fagin (on the one hand) and Glebskii, Kogan, Liogon and Talanov (on the other). In my opinion, the best source for this theorem is the excellent book by Joel Spencer "The Strange Logic of Random Graphs"... needless to say this is not but the tip of the iceberg. Xaman 23:32, 3 May 2006 (UTC)
[edit] What does percolation have to do with random graphs ?
And why is there a "blah blah blah etc." ? Is this a case of vandalism ? I'm writing this on 29-4-2006. I'll wait for a couple of months and if the percolation part has not been explained by then, I'll erase it.
29-6-2006: I'm glad to see that the "blah blah" part has been erased but the reference to percolation has not been explained. I've read the article on "percolation" and although some things mentioned there do have a graph structure no connection is mentioned or is obvious specifically with random graphs. A lot of things have a graph structure and there's no more reason for percolation to be there than for dozens of other things. So I'm erasing the reference to it. I'll check again in the future to see if anyone objects.
04-11-2006: Percolation indeed has to do with random graphs. Suppose the graph grows with small-sized edges in something solid. What's the probability of any vertex touching the other side of the solid wall? That's percolation. And that's also r.g.62.118.128.63 01:12, 4 November 2006 (UTC)
[edit] Erdos-Renyi model
Is the Erdos-Renyi model related to random graphs? It would be great if the Erdos-Renyi model article would be created, as there are a bunch of articles which link to it. Oleg Alexandrov (talk) 16:45, 28 January 2007 (UTC)
