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.
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:
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.
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.
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.
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.
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.
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.**
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.
Coloring general graphs is, as I said in my last post, quite difficult. But if you can restrict the structure of the graph, you can change the problem in a way that makes it *much* easier. The classic example of this is *planar graphs*.
A planar graph is a graph which can be drawn on a plane with no edges crossing. Every planar graph is also the structural equivalent to a map, where the vertices corresponding to two countries on a map are adjacent if and only if the countries share a border in the map. (A border here has non-zero length, so two countries that only meet in a corner don’t share a border.) You can see an example of a map with its corresponding planar graph overlayed to the right.
1. **Thinking Plague: “The Aesthete”**: Thinking Plague is just plain *odd*. They’re
a hard-to-classify group. It’s got vocals, but instead of the vocals being the lead,
they treat voice as just another instrument. They’re often atonal, and when they’re
tonal, the chords are often very dissonant. They *sound* like they’re very influenced
by Robert Fripp’s guitar craft, and there’s a persistent rumour that their guitarist
is a crafty, but after the last time they came up in a FRT, he showed up in the
comments to say that he wasn’t. They’re definitely not a group that I’d recommend to
everyone, but if you’ve got the right kind of taste, they’re really quite remarkable.
2. **The Tap Room Trio, “The Blackberry Blossom/THe Ballina Lass”**: very traditional
Irish music by a trio including my favorite traditional flutist, the great Harry
Bradley. Very simple traditional arrangements of classic Irish tunes.
3. **Tortoise, “It’s All Around You”**: Tortoise is a very influential post-rock
band. Given how much I like post-rock, and how much of what I listen to is
supposedly influenced by Tortoise, I expected to really like them. I find this
to be incredibly dull – downright trite.
4. **Gentle Giant, “A Reunion”**: Progressive rock with strong madrigal influences.
GG is brilliant.
5. **Sigur Rós, “Andvari”**: Post-rock from a mellow Icelandic band. This is more like what postrock is supposed to be to me. It’s very mellow and subdued, but it’s got a
real depth and sophistication. Beautiful track.
6. **King Crimson, “The Howler”**: a track off of Beat, the second-album by Discipline-era KC. Very typical of the vocal tracks from that phase of KC: lots of
Fripp’s tape loops setting the structure of the track; Belew doing his crooning voice.
7. **Naftule’s Dream, “Something is There”**: Brilliant neo-Klezmer, for lack of a better word. Naftule’s Dream is named after Naftule Brandwine, the genius of Klezmer clarinet; they’re a modern band that plays stuff clearly inspired by Klezmer, but filtered
through a lens of modern jazz and some rock. There’s some Ornette Coleman and Some Robert Fripp in here, mixed with the klez. Highly recommended.
8. **Sonic Youth, “Mildred Pierce”**: If you know what Sonic Youth sounds like, this
is absolutely typical of their sound. If you don’t know, you should check it out.
They’re strange, harsh, loud, and very, very good.
9. **Dirty Three, “Dream Evie”**: one of my favorite postrock groups, playing in the
more classically inspired vein of PR; Dirty Three is always wonderful.
10. **Mogwai, “With Portfolio”**: another favorite PR band; this one comes from the more
rock-oriented side of things
Graph coloring is deceptively simple. The idea of coloring a graph is very straightforward, and it seems as if it should be relatively straightforward to find a coloring. It turns out to not be – in fact, it’s extremely difficult. A simple algorithm for graph coloring is easy to describe, but potentially extremely expensive to run.
So that 8-facts thing is going around, and I got tagged. I’ve stalled long enough that everyone I read was already tagged, and I’m sure you’ve all seen it by now, so I’m not going to waste time repeating the rules or tagging anyone else.
1. One of my favorite things to do is cook. In fact, during grad school, when
I was particularly frustrated with my (then) advisor, I considered dropping out
of grad school and opening a restaurant.
2. It took three advisors for my to do my PhD. I started grad school with an offer
to work with one professor who did network protocol specification; by the end of my
first year, I was pretty sure that I didn’t want to keep working on that. I switched
to work with a theoretician on a strange computer architecture problem. He was a
total lunatic, and he really wasn’t interested in what I was working on – it was
work that he really wanted someone to do, but he didn’t really want to spend his time
thinking about it. Thank goodness, right around the time I became totally fed up,
the department hired a new faculty member, Lori Pollock, and within days of her
accepting the job, I was in her office asking her to be my advisor. I spend the next
four years working with her, and I still think she’s amazing. Best advisor ever!
(And I don’t even think she reads my blog!)
3. I can’t read maps. Not at all. They’re utterly meaningless to me. I’m a bit
learning disabled – I’ve got what’s called a perceptive impairment. One of the
problems that that’s caused me is the total inability to read maps, or catch balls.
4. I’m a musical instrument nut. I’ve got about 30 different tinwhistles, including
at least one in every key, two top-grade hand-made D whistles, and two giant low-D
whistles, two wooden flutes, 3 bamboo flutes, a magnificent selmer signature B-flat
clarinet, an old no-name A clarinet, 3 different antique albert clarinets,
a bluegrass banjo, and 2 Irish tenor banjos.
5. The first time I ever saw a real computer was in 6th grade. A classmate’s parent
brought it in to show my class. I was fascinated *instantly* by the idea of this thing
that I could teach to do math.
6. I like to build model airplanes out of paper. Not folded flying airplanes, but
very accurate, detailed scale models. For example, I’ve got a model of SpaceShipOne
which is about 5 inches long, made entirely of paper, down to the open landing gear
covers and struts.
7. I’m a huge fan of sculptor [Alexander Calder][calder]. Calder is best known for his
wonderful mobiles. The way that I discovered Calder was… the cover of my grad school
algorithms textbook. (My office mates and I just bought a replica of a Calder piece
to decorate our space.)
8. My wife and I got engaged one month to the day after we started dating. We didn’t
tell anyone except a few close friends for quite a while, because we didn’t think
her parents would accept it that quickly. We’d been friends for quite a while before
we started dating, but I’d never even considered asking her out, because she was
seeing someone else. Then she broke up with her ex-boyfriend, and showed up on my
doorstep the next morning, and pretty much never left.
[calder]: http://www.calder.org/
