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
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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.…
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…
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…
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…
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…
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…
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…
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,…
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-…
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…
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!
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 *…
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…
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…
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…
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…
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…
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…
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…
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…