Posts Tagged ‘math.LO’

The importance of choosing the right model

December 13, 2009

I’ve had the idea for this post bouncing around in my head for several months now, but now that I don’t have classes to worry about I can finally get around to writing it. I want to talk about some “pathological examples” in computer science, in particular in complexity and computability theory.

I wanted to post a picture of William H. Mills with this post, in the spirit of Dick Lipton’s blog. Unfortunately I can’t find one! Mills was a student of Emil Artin in the ’40s; he finished his thesis in 1949 and promptly (as far as I can tell) disappeared until the ’70s, when we find some work by a William H. Mills on combinatorial designs. After this, there’s nothing of note until Dr. Mills passed away several years ago at the age of 85.

While his work (assuming it’s his) on combinatorial designs looks interesting, W.H. Mills’ small place in history is assured by a short and unassuming paper from 1947, published when he was still a student. In this paper he showed that there’s a constant, which he called A, such that [A^{3^n}] is prime for all integers n \geq 1. Nowadays it’s called Mills’ constant.

(more…)

Where do graphs live?

December 5, 2009

This post came out of some thoughts I posted (anonymously, but mostly because I didn’t feel like registering) over at nLab. I don’t think it’s a secret that I’m heavily interested in the relationships between category theory and combinatorics, and more generally the ways in which we can use “structured” algebraic objects and “continuous” topological objects to gain information about the unstructured discrete objects in combinatorics. That said, the folks over at the nLab work on some crazy abstract stuff, which seems about as far away as possible from the day-to-day realities of graph theory or set systems. And maybe it is — but I hope it’s not, and as far as I’m concerned, this is a windmill that deserves to be tilted at. (After all, it might be a giant.)

So as my jumping-off point, I’ll take my observation from last time that the relationship between graphs and digraphs is analogous to the one between groupoids and categories. I briefly mentioned something called a quiver, which can be thought of as any of the following:

  • Another name for a digraph, which categorical people use when they don’t want us combinatorialists stomping in and getting the floor all muddy;
  • A “free category,” i.e., one in which there are no nontrivial relations between composition of morphisms;
  • An algebraic object whose representations we want to consider; it’s worth thinking of this way mostly because of the “freeness,” although if you try to define it more formally you’ll probably end up with the previous definition;
  • What you get when you take (part of) a category and forget all the rules for how morphisms compose.

This last point is the most interesting one for our purposes, since it’s clearly an algebraic object but isn’t as restrictive as “free category,” and thus has a chance of capturing the unstructured behavior of the combinatorial zoo. But it’s tricky to turn this into a rigorous definition that actually includes everything we want to be a quiver… so we’ll just use “quiver” as a fancy name for “digraph.” However, there’s an important philosophical lesson to be learned from the final point, so I’ll set it off:

Philosophical lesson. The edges of a quiver shouldn’t carry any information except for the vertices they are incident to; more generally, paths in a quiver shouldn’t carry any information except for their sequence of vertices.

(more…)