Monthly Archives: July 2007

Friday Random Ten, July 13th

1. **Marillion, “If My Heart Were a Ball It Would Roll Downhill”**: Very neat track from
one of my favorite neo-progressive bands. Catchy, but with lots of layers.
2. **Mandelbrot Set, “Constellation of Rings”**: math-geek postrock. What’s not to love?
3. **The Police, ;Every Breath You Take”**: I’ve always been a fan of the Police. But
what I like most about this song is how often it’s been used by clueless people. I’ve
heard this at multiple weddings, where the couple thought it was a beautiful romantic
song. If you listen to it, it’s anything but romantic. It’s actually a rather evil
little song about a stalker: “Every breath you take, every vow you break,
every smile you fake, I’ll be watching you… Oh can’t you see, you belong to me?”
How can anyone miss that?
4. **Naftule’s Dream, “Speed Klez”**: John Zorn-influenced klezmer mixed with
a bit of thrash. Insane, but very very cool. Thrash with a trombone line!
5. **Jonathan Coulton, “Todd the T1000″**: Sci-fi geek pop. It’s a catchy little pop
song about trading in your old robot for a new one which turns out to be a
6. **Hamster Theater, “Reddy”**: A short track from a great band. Hamster Theater
is a sort-of spin-off from Thought Plague. It’s a bit more traditional than
what you’d hear from TP; still very dissonant, sometimes atonal, but more often
closer to traditional tonality and song structure. This track is a short instrumental
featuring an accordion solo.
7. **Transatlantic, “Mystery Train”**: great little song. It’s a track by one of
those so-called supergroups; Transatlantic is a side-project formed by members of
Marillion (bassist Pete Travawas), Dream Theater (drummer Mike Portnoy), Spock’s Beard (singer Neil Morse), and the Flower Kings (guitarist Royne Stolt). In general, these
supergroups have a sort of shaky sound. These guys are *great* together; it sounds
like they’ve been playing together for years: they’re sharp, there’s a great interplay
between the different instruments, it’s all incredibly precise. I’ve heard that the
music was written in advance mainly by Morse, but even with polished music pre-written,
it’s got a great sound, and you can here the distinctive musical voices of each of the
8. **Godspeed You! Black Emperor, “Antennas To Heaven”**: It’s Godspeed – which means
that it’s brilliant post-rock. This starts off with a very rough recording of a very
old-timey folkey tune, and uses it as a springboard into a very typical God-speed
9. **The Flower Kings, “Devil’s Playground”**: more neo-progressive stuff. This is an
incredibly long piece (25 minutes), very typical of Roine Stolt’s writing. It’s not
the sort of way-out-there kind of thing that you’d hear from, say, King Crimson; it’s
very structured, very melodic, but put together more in the structure of a symphony
(theme, development, restatement) than the typical ABACAB structure of a rock song.
10. **Porcupine Tree, “Sleep Together”**: a brilliant song by yet another neo-prog
band. Very odd… a strange electronic pulse drives the entire song; but it starts
off as a very quiet song with this electronic pulse giving it a tense feel. Then
the percussion comes in, and shifts your sense of the rhythm… And then it gets
to the chorus, which is big and loud, and features a full string section. Strange,
but wonderful.

Fractal Borders

Part of what makes fractals so fascinating is that in addition to being beautiful, they also describe real things – they’re genuinely useful and important for helping us to describe and understand the world around us. A great example of this is maps and measurement.

Suppose you want to measure the length of the border between Portugal and Spain. How long is it? You’d think that that’s a straightforward question, wouldn’t you?

It’s not. Spain and Portugal have a natural border, defined by geography. And in Portuguese books, the length of that border has been measured as more than 20% longer than it has in Spanish books. This difference has nothing to do with border conflicts or disagreements about where the border lies. The difference comes from the structure of the border, and way that it gets measured.

Natural structures don’t measure the way that we might like them to. Imagine that you walked the border between Portugal and Spain using a pair of chained flags like they use to mark the down in football – so you’d be measuring the border on 10 yard line segments. You’ll get one measure of the length of the border, we’ll call it Lyards

Now, imagine that you did the same thing, but instead of using 10 yard segments, you used 10 foot segments – that is, segments 1/3 the length. You won’t get the same length; you’ll get a different length, Lfeet.

Then do it again, but with a rope 10 inches long. You’ll get a *third* length, Linches.

Linches will be greater than Lfeet, which will be greater that Lyards.


The problem is that the border isn’t smooth, it isn’t a differentiable curve. As you move to progressively smaller scales, the border features progressively smaller features. At a 10 mile scale, you’ll be looking at features like valleys, rivers, cliffs, etc, and defining the precise border in terms of those. But when you go to the ten-yard scale, you’ll find that the valleys divide into foothills, and the border line should wind between hills. Get down to the ten-foot scale, and you’ll start noticing boulders, jags in the lines, twists in the river. Go down to the 10-inch scale, and you’ll start noticing rocks, jagged shapes. By this point, rivers will have ceased to appear as lines, but they’ll be wide bands, and if you want to find the middle, you’ll need to look at the shapes of the banks, which are irregular and jagged down to the millimeter scale. The diagram above shows a simple example of what I mean – it starts with a real clip taken from a map of the border, and then shows two possible zooms of that showing more detail at smaller scales.

The border is fractal. If you try to measure its dimension, topologically, it’s one-dimension – the line of the border. But if you look at its dimension metrically, and compute its Hausdorff dimension, you’ll find that it’s not 2, but it’s a lot more than 1.

Shapes like this really are fractal. To give you an idea – which of the two photos below is real, and which is generated using a fractal equation?


Fractal Woo: Video TransCommunication

This is a short one, but after mentioning this morning how woo-meisters constantly invoke
fractals to justify their gibberish, I was reading an article at the 2% company
about Allison DuBois, the supposed psychic who the TV show “Medium” is based on. And that
led me to a perfect example of how supposed fractals are used to justify some of the
most ridiculous woo you can imagine.

Continue reading

The Mandelbrot Set


The most well-known of the fractals is the infamous Mandelbrot set. It’s one of the first things that was really studied as a fractal. It was discovered by Benoit Mandelbrot during his early study of fractals in the context of the complex dynamics of quadratic polynomials the 1980s, and studied in greater detail by Douady and Hubbard in the early to mid-80s.

It’s a beautiful example of what makes fractals so attractive to us: it’s got an extremely simple definition; an incredibly complex structure; and it’s a rich source of amazing, beautiful images. It’s also been glommed onto by an amazing number of woo-meisters, who babble on about how it represents “fractal energies” – “fractal” has become a woo-term almost as prevalent as “quantum”, and every woo-site that babbles about fractals invariably uses an image of the Mandelbrot set. It’s also become a magnet for artists – the beauty of its structure, coming from a simple bit of math captures the interest of quite a lot of folks. Two musical examples are Jonathon Coulton and the post-rock band “Mandelbrot Set”. (If you like post-rock, I definitely recommend checking out MS; and a player for brilliant Mandelbrot set song is embedded below.)

So what is the Mandelbrot set?


Take the set of functions
f_C(x) = x^2 + C where for each f_C, C is a complex constant. That gives an infinite set of simple functions over the complex numbers. For each possible complex number C, you look at the recurrence relation generated by repeatedly applying f, starting with x=0:

  1. m(0,C)=f_C(0)
  2. m(i+1,C)=f_C(m(i, C))

If m(i,C) doesn’t diverge (escape) towards infinity as i gets larger, then the complex number C is a member of the Mandelbrot set. That’s it – that simple definition – repeatedly apply f(x)=x^2 + C for complex numbers – produces the astonishing complexity of the Mandelbrot set.

If we use that definition of the Mandelbrot set, and draw the members of the set in black, we get an image like the one above. That’s nice, but it’s probably not what you expected. We’re all used to the beautiful colored bands and auras around that basic pointy black blob. Those colored regions are not really part of the set.


The way we get the colored bands is by considering *how long* it takes for the points to start to diverge. Each color band is an escape interval – that is, some measure of how many iterations it takes for the repeated application of f(x) to diverge. Images like the ones to the right and below are generated using various variants of escape-interval colorings.




My personal favorite rendering of the Mandelbrot set is an image called the Buddhabrot. In the Buddhabrot, what you do is look at values of C which *aren’t* in the mandebrot set. For each point m(i,C) before it escapes, plot a point. That gives you the escape path for the value C. If you take a large number of escape paths for randomly selected values of C, and you plot them so that the brightness of a pixel is determined by the number of escape paths that cross that pixel, you get the Budddhabrot. It’s fascinating because it reveals the structure in a particularly amazing way. If you look at a simple unzoomed image of the madelbrot set, what you see is a spiky black blob; the actually complexity of the structure isn’t obvious until you spend some time looking at it. The Buddhabrot is more obvious – you can see the astonishing complexity much more easily.


An Unsolved Simple Graph Problem

One of the things that I find fascinating about graph theory is that it’s so simple, and
yet, it’s got so much depth. Even when we’re dealing with the simplest form of a graph – undirected graphs with no 1-cycles, there are questions that *seem* like that should be obvious, but which we don’t know the answer to.
For example, there’s something called the *reconstruction theorem*. We strongly suspect that it’s really a theorem, but it remains unproven. What it says is a very precise formal version of the idea that a graph is really fully defined by a canonical collection of its subgraphs.

Continue reading

An Introduction to Fractals


I thought in addition to the graph theory (which I’m enjoying writing, but doesn’t seem to be all that popular), I’d also try doing some writing about fractals. I know pretty much nothing about fractals, but I’ve wanted to learn about them for a while, and one of the advantages of having this blog is that it gives me an excuse to learn about things that that interest me so that I can write about them.

Fractals are amazing things. They can be beautiful: everyone has seen beautiful fractal images – like the ones posted by my fellow SBer Karmen. And they’re also useful: there are a lot of phenomena in nature that seem to involve fractal structures.

But what is a fractal?

The word is a contraction of fractional dimension. The idea of that is that there are several different ways of measuring the dimensionality of a structure using topology. The structures that we call fractals are things that have a kind of fine structure that gives them a strange kind of dimensionality; their conventional topological dimension is smaller than their Hausdorff dimension. (You can look up details of what topological dimension and Hausdorff dimension mean in one of my topology articles.) The details aren’t all that important here: the key thing to understand is that there’s a fractal is a structure that breaks the usual concept of dimension: it’s shape has aspects that suggest higher dimensions. The Sierpinski carpet, for example, is topologically one-dimensional. But if you look at it, you have a clear sense of a two-dimensional figure.


That’s all frightfully abstract. Let’s take a look at one of the simplest fractals. This is called Sierpinski’s carpet. There’s a picture of a finite approximation of it over to the right. The way that you generate this fractal is to take a square. Divide the square into 9 sub-squares, and remove the center one. Then take each of the 8 squares around the edges, and do the same thing to them: break them into 9, remove the center, then repeat on the even smaller squares. Do that an infinite number of times.

When you look at the carpet, you probably think it looks two dimensional. But topologically, it is a one-dimensional space. The “edges” of the resulting figure are infinitely narrow – they have no width that needs a second dimension to describe. The whole thing is an infinitely complicated structure of lines: the total area covered by the carpet is 0! Since it’s just lines, topologically, it’s one-dimensional.

In fact, it is more than just a one dimensional shape; what it is is a kind of canonical one dimensional shape: any one-dimensional space is topologically equivalent (homeomorphic) to a subset of the carpet.

But when we look at it, we can see it has a clear structure in two dimensions. In fact, it’s a structure which really can’t be described as one-dimensional – we defined by cutting finite sized pieces from a square, which is a 2-dimensional figure. It isn’t really two dimensional; it isn’t really one dimensional. The best way of describing it is by its Hausdorff dimension, which is 1.89. So it’s almost, but not quite, two dimensional.

Sierpinski’s carpet is a very typical fractal; it’s got the traits that we use to identify fractals, which are the following:

  1. Self-similarity: a fractal has a structure that repeats itself on ever smaller scales. In the case of the carpet, you can take any non-blank square, and it’s exactly the same as a smaller version of the entire carpet.
  2. Fine structure: a fractal has a fine structure at arbitrarily small scales. In the case of the carpet, no matter how small you get, it’s always got even smaller subdivisions.
  3. Fractional dimension: its Hausdorff dimension is not an integer. Its Hausdorff dimension is also usually larger than its topological dimension. Again looking at the carpet, it’s topological dimension is 1; it’s Hausdorff dimension is 1.89.

Graph Contraction and Minors

Another useful concept in simple graph theory is *contraction* and its result, *minors*
of graphs. The idea is that there are several ways of simplifying a graph in order to study
its properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.

Continue reading

Graph Decomposition and Turning Cycles

One thing that we often want to do is break a graph into pieces in a way that preserves
the structural relations between the vertices in any part. Doing that is called
*decomposing* the graph. Decomposition is a useful technique because many ways
of studying the structure of a graph, and many algorithms over graphs can work by
decomposing the graph, studying the elements of the decomposition, and then combining
the results.
To be formal: a graph G can be decomposed into a set of subgraphs {G1, G2, G3, …}, where the edges of each of the Gis are
*disjoint* subsets of the edges of G. So in a decomposition of G, *vertices* can be shared between elements of the decomposition, but *edges* cannot.

Continue reading

Edge Coloring and Graph Turning

In addition to doing vertex and face colorings of a graph, you can also do edge colorings. In an edge coloring, no two edges which are incident on the same vertex can share the same color. In general, edge coloring doesn’t get as much attention as vertex coloring or face coloring, but it can be an interesting subject. Today I’m going to show you an example of a really clever visual proof technique called *graph turning* to prove a statement about the edge colorings of complete graphs.
Just like a graph has a chromatic index for its vertex coloring, it’s got a chromatic
index for its edge coloring. The edge chromatic index of a graph G is the minimum number of colors in any edge-coloring of G. The theorem that I’m going to prove for you is about the edge chromatic index of complete graphs with 2n vertices for some integer n:
**The edge-chromatic index of a complete graph K2n = 2n-1.**

Continue reading

A Taxonomy of Some Basic Graphs

Naming Some Special Graphs
When we talk about graph theory – particularly when we get to some of the
interesting theorems – we end up referencing certain common graphs or type of graphs
by name. In my last post, I had to work in the definition of snark, and struggle around
to avoid mentioning another one, so it seems like as good a time as any to run through
some of the basics. This won’t be an exciting post, but you’ve got to do the definitions sometime. And there’s a bunch of pretty pictures, and even an interesting simple proof or two.

Continue reading