9
$\begingroup$

One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a symmetric matrix. However, to get it's shape, you'd need a collection of row/column permutations, which makes a matrix a little less suited. It's also a bit harder to 'see' the graph, once it's in that form.

My question is: Are there any 'graphical' algebras that can describe the 'shape' of graphs?

What I'm thinking of is what kinds of formal systems that algebraic topologists tend to come up with. In particular, things like the algebra for knot invariants, or notational systems like operads or polygraphs. These kind of 'doodle algebras' are not nearly as well developed, so perhaps there is a reason to believe that no such algebra exists for graphs, but I'd though I'd ask before assuming otherwise.

UPDATE:

My question is probably very narrow and not immediately answerable with a 'yes', so if the moderators don't mind, I'll broaden it by asking:

Are there any existing systems (the kind I describe above) that could be adapted (easily or otherwise) to create such a system? If there's more than one, feel free to mention all of them. And throw in the ones already mentioned as well.

Motivation

My motivation for such a question is actually about classifying asymmetric graphs. I'm only an undergrad, so my review of the current state of algebraic graph theory is pretty thin. But I've yet to see much, if any, work in trying to systematically describe all graphs in an algebraic way, and in particular, one that uses visual metaphors over symbolic ones.

Practical example where such a system would be useful

Suppose one wants to describe a proof that all Eulerian graphs must have vertices of even degree. A standard proof usually uses arguments about even and odd degrees, without mentioning the actual edges used. A typical student would find such a proof for the first time, and probably begin drawing graphs, attempting to convince himself of the argument. But perhaps a better tool than the pure 'logical' argument, would be to show that any collection of 'symbols' from such a language could not satisfy some 'completeness' condition.

Yeah, I know, I'm being hand-wavy at this last part.. If I wasn't, though I'd probably start creating such a system myself!

But ignoring my vagueness for a moment, I get a sense that many of the old and well known theorems in graph theory are not difficult but require some conceptualization that a really good framework could 'tie up' and 'package' into a unified view.

Improve this question
$\endgroup$
9
  • $\begingroup$ I feel as if this question, though it is related to the graph isomorphism problem, may be better suited for mathoverflow or math.se. $\endgroup$ – bbejot May 11 '11 at 4:44
  • 3
    $\begingroup$ While it's possible that you might get better answers on mathoverflow, we do have discussions on graph representations here, and I don't see a reason to move it. $\endgroup$ – Suresh Venkat May 11 '11 at 5:32
  • 4
    $\begingroup$ are you looking for something like Coxeter-Dynkin diagrams but for graphs? $\endgroup$ – Artem Kaznatcheev♦ May 11 '11 at 10:31
  • $\begingroup$ On re-examination, my question is actually very narrow, and I'm willing to bet is not answerable with a 'yes' at the moment, although there are probably a number of things very close to what I'm imagining. I'll re-adapt my question for that. $\endgroup$ – robinhoode May 12 '11 at 0:31
  • $\begingroup$ @Artem Yes, that's actually very close to what I'm thinking of. $\endgroup$ – robinhoode May 12 '11 at 0:31
6
$\begingroup$

Many people have tried to find an algebraic language to describe the shape of a graph. This question is essentially the one that motivates structural graph theory.

At the heart of this area of discrete mathematics is the study of graph decompositions. Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.

Particular kinds of graph decompositions have led to some of the most general results in graph theory. For instance, one of the main technical tools developed for the graph minors project, which led to the Robertson-Seymour theorem, is the graph structure theorem. This shows that classes of graphs that exclude some minor can be built up from simpler graphs.

In the proof of the Strong Perfect Graph theorem a somewhat different decomposition was used. The key result is: For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.

The decompositions studied to date are in some sense non-algebraic. My personal intuition is that there are indications that there is no "nice" system such as the one you seek. Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).

Improve this answer
$\endgroup$
0
$\begingroup$

This question is important in functional programming since usual representation of graphs are inelegant and inefficient to use in purely functional languages.

A nice approach was presented at ICFP last year: "Algebraic Graphs with Class (Functional Pearl)", by Andrey Mokhov.

I don't know if it fully answers your needs, but it can represent algebraically a wide range of different types of directed and undirected graphs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.