From the official MySQL documentation comes perhaps the highest combination of software-project-respectability and ugliness-of-officially-recommended-hack that I’ve yet encountered:

To retrieve all rows from a certain offset up to the end of the result set, you can use some large number for the second parameter. This statement retrieves all rows from the 96th row to the last:

SELECT * FROM tbl LIMIT 95,18446744073709551615;

My recent frolicking about with Graph Theory was facilitated by a database that I populated from these collections, as well as web interface to it with some basic search functions. I just finished polishing the interface to meet my own user-friendliness standards, and have propped it up in the Sandbox here.

It has all of the undirected connected simple graphs with nine vertices or fewer (except the graph with one vertex, which I doubt anyone is interested in), and allows browsing through the database with just about any simple restriction on the attributes of the graph (radius, girth, automorphisms, etc.).

Having the graphs and their attributes pre-computed means that it can be a lot faster to find graphs with particular combinations of characteristics than it would be if everything had to be computed on the fly. It’s also easy to find types of graphs that don’t exist for nine vertices or less, such as asymmetric regular graphs.

As someone with little academic experience with graph theory, I found it a very efficient way to get acquainted with the different types of graph properties and generally increase my familiarity with the subject.

It also tended to prompt deeper questions that aren’t so easy to Google for. For example, I noticed that very few of the graphs had an automorphism-count that was a prime higher than two. Specifically, there are only four of them, all with only three automorphisms, and all on nine vertices. This is one of those:

The smallest graph with 2 automorphisms is actually the smallest graph with any edges at all, which is the only connected graph on 2 vertices. So if we form a sequence of the order of the smallest graph with p automorphisms for all primes p, we have the following so far:

2, 9, …

So how does this continue? What is the smallest graph with exactly 5 automorphisms? 7? 11? I can’t find any information on it, but I have to think they might be quite large, such that it would be hard to find them without more sophisticated mathematical analysis. On the hand, they might all be simple variations on the one above.

To avoid the temptation to write a new blog post every time I see an interesting graph, I’ll probably create a list for them. For now, the large-girthed-graphs are fun.

I like Dell’s approach to comparing-and-contrasting their product lines:

The fun continued when I tried to start customizing things:

I’m not sure if I should be embarrassed or not, but I think these things are cute:

I’ve always wanted an excuse to piddle about with graph theory, so when my multi-agent systems class inspired me to think of a naïve attempt at solving the graph-isomorphism problem, I had to try it.

The inspiration was a network routing algorithm where each node in the network keeps a table of the distances to the other nodes through each of its links. I had to wonder if it would be possible to reconstruct the network simply based on one node’s view of the distances. That doesn’t seem very likely, but if we use that information from all of the nodes, I suspect it may even be trivial.

That’s a slightly different question from the graph isomorphism problem though, because a network is labeled, while an unlabeled graph is not. It does, however, suggest a graph invariant that would solve the graph isomorphism problem provided that any two non-isomorphic graphs produce a different invariant.

The invariant is constructed as a three dimensional array by simply listing, for each vertex, the shortest-path distances to the other vertices through each of its edges. The array is then recursively sorted to normalize it. This gives an invariant with seemingly an awful lot of information (at least in my inexperienced opinion). It didn’t seem probable however, that someone with almost no experience in graph theory had solved one of the biggest open problems in graph theory, so I set out to find a counterexample.

Specifically, I was looking for the smallest pair of non-isomorphic graphs that shared the same invariant. I set one of the computers at my disposal to work on it, and found that the invariant is complete for all graphs with less than nine vertices. For nine-vertex graphs, there are no less than twenty pairs of counterexamples. Here is the pair with the least number of edges:

The invariant guarantees a few things about these two graphs. They must be the same size and of the same order (same number of edges and vertices), and they must have the same set of edges incident on its vertices: in this case, we can see that both graphs have 6 vertices with 4 edges, 2 vertices with 3 edges, and 1 vertex with 2 edges.

We can tell that the graphs are not isomorphic with a little inspection: if they were isomorphic, then the blue vertices must correspond, since they are the only vertices with two edges. Then the pairs of vertices marked in red must correspond to each other (without knowing which to which), being the two vertices connected to the only vertex with two edges. In both graphs, there are two other vertices that are both connected to the red pair, which are the vertices marked in green. Then there is a third pair of vertices which are connected to one of the red vertices, but not both. These are marked in yellow. Notice that in the first graph, the green and yellow pairs do not share an edge, but in the second graph they do. Therefore, the graphs are not isomorphic.

Showing that they share the same invariant would be a much more laborious task, so I’m going to trust the computer on this one.

This makes me want to start a collection of graph invariants and their corresponding smallest pair of “counterexamples”.

Just because I like pictures of graphs, here’s another one of the twenty pairs I found: