David's Blague

A graph is a kind of model that contains edges and vertices. It's reasonably easy to draw pictures of graphs, where each edge is a line, and each vertex is a little bubble, maybe with a label in it. I use the program Graphviz to do this, and it's satisfactory.

I've been spending some time thinking about hypergraphs, which are a generalization of graphs, in which a hyperedge might connect more than two vertices. It was already true in a graph that a vertex might "connect" more than two edges, and this remains true in a hypergraph.

It's a bit tougher to draw a picture of a hypergraph, for the same reason it's hard to draw pictures of hypercubes or hyperspheres: the simplicity of the structure cannot be captured in a two-dimensional projection. Simple hyperstructures start to look complex when rendered in only two dimensions. For instance, consider a unit hypercube: each edge being of length one. Each surface of the hypercube is a cube, which is easy enough to draw, but that is only one surface of the hypercube, which is sort of like drawing a square to represent a plain old cube.

But I digress.

The question is this: difficulty of drawing the pictures aside, doesn't it make sense to collapse the hyperedge and hypervertex into a single concept for a hypergraph?

Basically, I think a hypergraph is simpler than a graph, because it lacks any distinction between edges and vertices. But maybe I'm thinking about it wrong. If you are Reinhard Diestel and you've stumbled along to this post, could you possibly clear that up for me? Comments are open.

Labels: graph theory

While rehearsing for my presentation at the Emerging Tech conference, it came clear to me that the term "cellular automata" is in that awful, yet oddly ubiquitous class of scientific terms that explain exactly nothing to the lay person.

I am all for obfuscation when it serves some purpose, but in this particular case, the term doesn't do much for hackers, either. Lacking a PhD, I can't speak for them, but the only purpose I can imagine such a term would serve, is to make the speaker sound "really smart" (read: like a pompous ass). The term was coined by a guy whose first language was abstract math, with Hungarian as a close second- not exactly the poster children of clarity.

Here is where I've arrived so far. It still needs polish:

A cellular automaton is a graph, with each node (cell) on the graph containing exactly one member of a finite set (value). The state of the model is completely specified by the values of each cell. The value of a cell is updated by applying a rule to the values of its neighboring cells.

My objection to other descriptions I read are not entirely overcome by my own description. I have used the words "graph" and "node" from graph theory, and implied the word "vertex" without using it by using the phrase "neighboring cells."

Not perfect.

But better than some. My big objections to other descriptions is that they include too much math, physics, or biology to be considered generally useful abstractions. After all, one of my favorite models in this class is from a social scientist.

Labels: cellular automata, discrete models, etech, graph theory