Mark Chu-Carroll is a Computer Scientist working as a researcher in a corporate lab. My professional interests run towards how to build programming languages and tools that allow groups of people to work together to build large software systems.
goodmath
Posts by this author
July 17, 2007
I just finally got my copy of Mandelbrot's book on fractals. In his discussion of curve fractals (that is, fractals formed from an unbroken line, isomorphic to the interval (0,1)), he describes them in terms of shorelines rather than borders. I've got to admit
that his metaphor is better than…
July 16, 2007
One application of graph theory that's particularly interesting to me
is called Ramsey theory. It's particularly interesting as someone who
debunks a lot of creationist nonsense, because Ramsey theory is in
direct opposition to some of the basic ideas used by bozos to
purportedly refute evolution…
July 15, 2007
Today, I'm going to talk a bit about two closely related problems in graph theory: the maximal clique detection problem, and the maximal common subgraph problem. The two problems are interesting both on their own as easy-to-understand but hard-to-compute problems; and also because they have so…
July 14, 2007
Yesterday's Wall Street Journal has a *spectacular* example of really bad math.
The WSJ is, in general, an excellent paper with really high quality coverage of economic issues. But their editorials page has long been a haven for some of the most idiotic reactionary conservative nonsense this side…
July 13, 2007
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…
July 12, 2007
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…
July 11, 2007
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% companyabout Allison DuBois, the supposed psychic who the TV show "Medium" is based on. And that
led me to a perfect example of how…
July 11, 2007
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…
July 10, 2007
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…
July 9, 2007
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…
July 8, 2007
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.…
July 4, 2007
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…
July 3, 2007
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…
July 2, 2007
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…
July 2, 2007
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…
June 29, 2007
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…
June 28, 2007
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…
June 28, 2007
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,…
June 27, 2007
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-…
June 26, 2007
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…
June 25, 2007
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!
June 25, 2007
Let's talk a bit about graphs, being a tad more formal about them.
A graph G is a pair (V,E) where V is a non-empty set of *objects* called vertices, and E is a set of pairs of elements of V called edges where a pair x={a,b} means that
vertices a and b are *adjacent*. We also say that edge x is *…
June 24, 2007
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…
June 22, 2007
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…
June 22, 2007
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…
June 21, 2007
So far, we've been talking mainly about the ZFC axiomatization of set theory, but in fact,
when I've talked about classes, I've really been talking about the von
Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other day that the ordinals are a proper class is an…
June 20, 2007
Part two of our crackpot's babblings are actually more interesting in their way, because they touch on a fascinating mathematical issue, which, unfortunately, Mr. Brookfield is compeletely unable to understand: the Poincare recurrence theorem.
Brookfield argues that the second law of…
June 19, 2007
As several of my fellow science-bloggers pointed out, William Dembski has written a post at Uncommon Descent extolling an "international coalition of non-religious ID scientists", and wondering how us nasty darwinists are going to deal with them.
Alas for poor Bill. I'm forced to wonder: is there…
June 17, 2007
With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite
ordinals using exponentiation. Exponentiation is defined in terms of
repeated multiplication, but it allows us to represent numbers that we
can't express in terms of any…
June 13, 2007
I'll continue my explanation of the ordinal numbers, starting with a nifty trick. Yesterday, I said that the collection of all ordinals is *not* a set, but rather a proper class. There's another really neat way to show that.
Remember that we defined the ordinal 0 as the empty set, ∅, and every…