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…
Graph Coloring Algorithms
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.
That Silly 8-Facts Thing
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…
Sewell's (not exactly a-) Law
In light of [my recent demolition of a purported improvement on the second law of thermodynamics][2l], an alert reader sent me [a link to this really boneheaded piece of work at Uncommon Descent by Granville Sewell][sewell].
[sewell]: http://www.uncommondescent.com/intelligent-design/introducing-sewells-law/
[2l]: http://scienceblogs.com/goodmath/2007/06/dembskis_buddy_part_2_murphys.php
Sewell is, yet again, trying to find some way of formulating IDist anti-evolution garbage in terms of the second law of evolution. Sewell’s been doing this for ages, and it’s been a
wretched failure. Naturally, according to Sewell that has *nothing* to do with the fact that his argument is a pile of rubbish – it’s all because people have been distracted by
arguments that came about because people don’t understand the second law of thermodynamics. It’s their confusion of 2LOT, *not* any flaw in Sewell’s argument.
So, he’s proposing a new law which he claims subsumes the 2LOT, and which he modestly names after himself:
Get out your crayons: it's graph coloring time!
One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
The variants of the vertex coloring problem are things like:
* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a graph?
* Given an integer N, can you find an N-coloring of the graph?
The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.
Wonderful Mobius Transformation Video
Via The Art of Problem-Solving, a great video on Mobius transformations. I never really got how the inversion transformation fit in with the others before seeing this!
The First Graph Theory Problem
Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.
Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
the city, there were seven bridges connecting the parts of the city. Is it possible to
take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?
PZ Has a Question: Is George Gilder Wrong About Network Theory?
PZ wrote about the latest nonsense from IDiot George Gilder. In this interview, Gilder tries to make some really horrible arguments about how everything is really hierarchical, and he uses “information theory, computer science, and network theory” as examples.
I believe that the universe is hierarchical, with creation at the top – the idea that there’s a creator and that we, at our best, act in his image. This top-down model is what all of my work has in common. I sensed that the basic flaw and failure of feminism was its gradient toward pure animal passion with no procreative purpose. In economics, I believed that it was the supply that created the demand. In my examination of computers and telecom, and subsequently biology, I saw the same thing. That’s really how I came into the intelligent design movement – through the recognition of this same structure that I’d previously examined in sexuality and economics, information theory, computer science and network theory.
PZ does a great job of tearing him down, but also asks:
Computer science and network theory: Gilder knows nothing about either, and has no training in the subjects. I suspect there are readers who know far more about the subject than Gilder: is network theory all about setting up strict hierarchies of top-down control?
And hey golly, that’s right smack dab in my area.
Network theory is seriously nifty stuff. It’s a sub-area of graph theory, which is one
of my favorite areas of computer science. And the short answer to PZs question is: “Hell no: in fact, if that *were* the case, it wouldn’t be an interesting subject at all. What makes it so interesting and difficult is precisely the fact that things aren’t hierarchical”.
Simple Pathology: Betterave
Sorry for the missed weeks of friday pathological programming language columns. To be honest, I’m running out of languages. I’m sure there must be more, but my usual sources (dealers?) are running out – so send links!
Anyway, today I’m going to look at a really simple one, which I find fun. It’s
not an overly exciting language, but it is a language which is has semantics almost as
trivially simple as [BrainFuck][bf], but which ends up looking almost as much like line-noise as [TECO][teco]. It’s called [Betterave][betterave].
[betterave]: http://www.esolangs.org/wiki/Betterave
[teco]: http://scienceblogs.com/goodmath/2006/09/worlds_greatest_pathological_l_1.php
[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php