Thursday, May 8, 2008

Connect the dots and the world will follow

Musing about connectivity and intelligence put me in mind of one of my favorite branches of mathematics (yep, I'm a geek -- that's "favorite branches of mathematics", plural): graph theory.

For those unfamiliar with the game, here's how it works. Take a bunch of dots and connect them with lines. The lines don't have to be straight, and they can cross each other. You can move the dots around however you like to make the picture clearer. All that matters is what's connected to what. If dot A is connected to dot B, it doesn't matter here how many lines you drew between the two, so let's just say there's never more than one. From this simple setup come many deep and interesting results (interesting to a math geek, at least).

Suppose you can connect each dot to at most one other dot (if you can't connect them at all, you've just got dots). In that case, you'll always end up with some number (maybe zero) of loose dots, and some number (maybe zero) of pairs of dots connected by a line.

Suppose you can connect each dot to at most two other dots. Then (after maybe re-arranging to get a clearer picture) you'll get three different things: loose dots, connected pairs and rings of three or more dots.

Now suppose you can connect each dot to at most three other dots. There are now infinitely many different possibilities, almost all of which are completely unknown except in a broad statistical sense. Even telling if two arrangements are the same or different is (in general) an intractable problem. Or at least we're pretty sure it is.

What if you can connect each dot to up to four (or five, or a million) different dots. Have you gained much? Not really. You can take any dot with more than three lines out and replace it with a ring of dots, each with one line out to the rest of the world.

In short, there are effectively only four levels of connectivity: zero (boring), one (boring), two (pretty boring) and three or more (infinitely complex). How connected the world is really only matters at one critical point.

No comments: