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.)