Is it true that anyone on the planet is connected to any other person on the planet through six degrees of separation? Why, or why not?
Well, it just so happens that there has been an experiment done on this. The original study was from Milgram back in the 1960s (same guy that did shock experiments). Orginal paper can be found here: http://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/travers_milgram.pdf However, the results are contentious. A Dr. Judith Kleinfeld has a good rundown on this. Her abstract starts out:
She concludes with:
I also recall watching a television program a while back where Mark Vidal of the Faber Institute distributed packages all over the world with instructions on how to get the package back to him by only sending it to people you knew (basically a repeat of the Milgram study). I do recall that he did get his packages back, and often in less than six steps. Although that may have been assisted for the TV show's production values.
I also found this paper from Cornell (The Small-World Phenomenon: An Algorithmic Perspective) that starts out as:
This paper makes a more mathematical look at it versus an experimental look, and thus concludes:
I also found some further studies, however, the sites require subscriptions: http://www.eric.ed.gov/ERICWebPortal/search/detailmini.jsp?nfpb=true&&ERICExtSearch_SearchValue_0=EJ744252&ERICExtSearch_SearchType_0=no&accno=EJ744252
So as I started off with, the results are contentious. A final conclusion may need more research.
Béla Bollobás, who is famous for having studied the properties of random graphs/networks with Paul Erdős (note Zenon's comment above), discovered loose bounds on the diameter of random regular graphs. He proved the following:
In our case, n would be the world population, which we can estimate at 6.93x109. The parameter r would be the minimum number of connections per person, which I think we can estimate at 130 (based on statistics from Facebook). Plugging in those values and solving for d we get
This bound strictly increases as ε → ∞, so taking the limit as ε → 0 gives us the least d that satisfies Theorem 1:
Therefore, by Theorem 1, the diameter of a graph on 6.93x109 vertices with degrees at least 130 almost surely has a diameter of at most 8.
According to Bollobás, this bound could even be sharpened (meaning that it is likely the actual value is lower than 8). The bound will of course also be tighter if people actually have more than 130 connections. Also note that this is a bound on the maximum degree of separation between people; the average degree would likely be much lower.
Summary: In a population of 6.93x109 in which each person is connected to at least 130 others, it can be said with extremely high confidence that the largest degree of separation between any two people is at most 8.
If we assume that the number of connections per person, r, remains constant at 130, then we can set d to 9 and solve for n to get an estimate on the size of the population when the maximum degree of separation will increase. This will happen when the population is just under 10 Trillion. Assuming our current rate of population growth remains constant at about 1.14% per year, our population should reach 10 Trillion in about 640 years. Therefore, I conjecture that in the year 2651 we will have to create the "Seven Degrees of Separation Game"! ;-)
Well since the graph is disconnected (that is, there are tribes of people who still have had no contact with the outside world), this statement can't be true, since there is no way to reach them from any of us.
Microsoft has performed an analysis of their IM network. They wrote:
Paper is available online: Planetary-Scale Views on an Instant-Messaging Network
Those are further readings in the matter.
Unfortunately, ibeatgarry.com is unavailable now, one was able to search the shortest chain he beat Garry Kasparov by (if I remember correctly) the Mega Database delivered by chessgames.com. My Kasparov-number was infinite when I checked it years ago (no beating way existed), I'm sure it is less now. The strongest player (~2100-2200 ELO-points) in my then-club had 5 or 6, I can't remember. But my non-beating, only playing number is 3, it seems to be extremely few. Kasparov -> Korchnoi -> Kádas -> me. I can't find the Korchnoi-Kádas match, but Gábor Kádas told me they played once. And I played with Gábor in 2007, if I remember correctly, but it is impossible to find, it happened in an unofficial rapidchess event. (Trivia: I lost that match! :))
It depends on what you mean by connected.
If you believe (and the numbers make sense) that we have all had air in our lungs which was also in those of Genghis Khan, for example, and you call that a connection, 6 is much greater than the real number, and everyone alive is probably connected by molecules directly or via one other person.
Example equation, referring to Caesar: http://www.j-bradford-delong.net/movable_type/archives/001392.html
If a connection means "having had a conversation with, in person" it's harder.
Another thing which needs to be addressed is the variety of social networks involved. One person has the internet, another person lives as a hunter-gatherer in the jungle. Boundaries also need to be taken into account. A North Korean citizen and a French citizen do not have the same chance of having a connection in India. French citizens have free access to internet, can leave their country at will, unlike citizens of North Korea.
Taking Milgrams case of the café in Tunisia, well it's a poor example. Both of the parties in conversation are privileged enough to travel to Tunisia from their respective homelands, which puts them in a minority, or a given class, if you're so inclined. Remember the case is in the 60's before the advent of high-volume, lower-cost flights. On top of that, their mutual connection, owning a chain of supermarkets, will have far greater influence than the average person, and is a far from typical case. However it does give an interesting lead in what may be the quickest way to find a connection.
If you have an algorithm where you take a person, then look for the most influential person they know, and repeat that for the next two connections, you should have a huge range of options available to you. You might want the remaining steps to focus on the individual at the other end.
So if you think having had the same molecules in your lungs is a connection, yes it is true. If not, it's probably a lot more complicated than has been suggested.