Current thinking, according to Dr. Hawking and those guys, is that the constants that define our universe, like the universal gravitational constant, were established when our universe formed. If another universe formed, it might have different constants, and, from them, different natural laws. A really interesting novel that includes this idea is The Gods Themselves by Isaac Asimov. One of the things about math is that it comes up with “laws” that hold in any imaginable universe. Occupy Math thinks this is at least a little bit cool and today’s post is about one of these laws that affects things like social networks, gossip, and at least one of Occupy Math’s research projects.
Math finds not universal laws, but multiversal laws. They are true from logic alone without a need for any other inputs.
Our topic today is the Kolmolgorov zero-one law. Consider a group of 300 people that start off with no social connections. We add random connections one at a time and look at the size of the largest connected network of people that forms. Since these experiments are random, we are going to do 100 of them and look at the average results.
The gray tracks are the individual experiments, the blue track is the average. The experiments uses 300 people so there are actually 44,850 possible connections (pairs of people). In spite of this, it only takes 600 connections to almost completely hook up the network. This is an example of a Kolmolgorov effect – in a tiny initial fraction of the range of the possible number of connections, the network goes from pretty much unconnected to completely connected. This is sudden! The zero in zero-one law is “unconnected” and the one is “connected”.
That is the essence of the zero-one law: an abrupt change from unconnected to completely connected.
What does this imply?
- When a social network forms, it starts off pretty thin and then suddenly explodes. My editor noticed this effect in the growth of her secret women’s professional networking Facebook group; it went from hundreds to thousands of members in a couple of short weeks.
- The network size diagram explains why gossip can spread so fast; even if only a small fraction of the people are willing to pass gossip along – roughly 2% – then the gossip will still end up almost everywhere. Increase the percentage of people willing to talk and the gossip gets everywhere sooner.
- Almost any system where connections can form has this property where at first, not much is going on, and then suddenly the connected network is huge (if it can grow) or highly connected (if it is among a fixed number of people).
A Kolmolgorov zero-one effect happened to Occupy Math last week. I was working on research with Lauren Taylor, a fourth-year student, where we are evolving puzzles by randomly connecting squares to make puzzle pieces. Here is a puzzle of the type we are trying to evolve, though this one is actually an example from the 1950s called Ten-Yen, currently available from Kadon enterprises.
We were evolving a specification of which of the 1×1 squares were connected to one another to form the puzzle pieces called polyominos. You may be familiar with the two-square polyominos which are called dominoes. Anyhow, when we scaled up from a 6×6 puzzle to a 10×10 and ran directly into a wall of Kolmolgorov. Look at these evolved puzzles:
|Three 6×6 puzzles|
Two ten by ten puzzles
Evolution was trying to make a puzzle with lots of small pieces, all different from one another. This worked fine for the 6×6 puzzles, but when the same software was set to working on a 10×10 puzzle, it produced the very bad puzzle with two pieces. In the code making the bad puzzle, evolution could not compensate for the zero-one law and suffered from too many connections. The good 10×10 puzzle used a different algorithm that used less connections – avoiding the zero-one effect – and rewarded diversity of pieces more strongly.
Usually when you debug a computer program, the problem is in your code. This time the bug was in the mathematical structure of reality. Bummer!
This post shows that knowledge of mathematical laws, multiversal laws, like the zero-one law, would let a programmer spot critical problems that are not actually in the code but in the structure of reality. The fact that these mathematical laws work everywhere has some odd implications.
My editor observed that even strange, purple creatures with tentacles, in the next universe over, will still have gossip networks that spread rumors really well. Go figure?
Occupy Math is trying to address issues on a large scale in this post, rather than working purely locally in our own universe. To be honest, the super-universality of math follows from its implacably abstract nature. If you’re interested in other laws of the multiverse, comment or tweet and we will see if we can find others that are interesting and explicable.
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics