A very interesting open problem in topology and combinatorics is to find out, for some given , what the inequality for a graph means, and in fact if it does mean anything at all for large . Here is the Colin de Verdière graph invariant, a minor-monotone invariant of spectral origin.

Known results are:

- iff is a disjoint union of paths;
- iff is outerplanar;
- iff is planar;
- iff is linklessly embeddable.

That’s very neat indeed! Unfortunately even guessing what it means for seems pretty hard. What is the next step after being planar and having no links ? ~~Having only one connected component ? Or maybe having no cycle ?~~ (*Update*: actually these two last ideas obviously wouldn’t work since they both imply linkless embeddability. Sigh.)

Advertisements

March 12, 2007 at 10:42 pm |

And what does linklessly embeddable mean?

March 13, 2007 at 12:36 pm |

See this for the definition of a link.

March 13, 2007 at 1:01 pm |

I knew what is link, wanted to know where it’s embeddable 🙂 But I guess it’s R^3 which somehow I coudn’t figure out yesterday 🙂

March 13, 2007 at 3:33 pm |

Yes, it’s as usual for knot theory, see the paper by Lovász and Schrijver here 😉

March 22, 2007 at 5:26 pm |

[…] de Verdière invarariant and Four-Color theorem This is a follow-up to a previous post on the Colin de verdière graph invariant. I’ve come across a book in french by Colin de […]