Talk:Random graph

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	High Priority	Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. The "Properties of random graphs" section needs to be expanded to say much more about the main results known for random graphs. The article could also do with some discussion of pseudorandom/quasirandom graphs, and should mention the random graph models used to generate small-world networks / scale-free networks (with links to those articles for more detail). Joseph Myers 01:19, 21 May 2007 (UTC)

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.

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)

[edit] visualizations

What this page really needs are some visualizations of random graphs versus other more organized graphs. You can see the difference when you look at them. Pwoolf (talk) 19:18, 8 May 2008 (UTC)