On learning of the lattice structure of the system of rooted spanning trees of a plane graph, I was hopeful that the theory would extend in a nice way to unrooted trees. For each choice of root and outer face, we have a distributed lattice, and the set of state transition systems formed in this way for different roots in a fixed graph share the same set of vertices and many of their edges. Different choices of root and outer face lead to different orientations on the edges, but we already know of an unoriented structure that generalizes distributed lattices, namely media. If we form a state transition system in which the states are the spanning trees of a plane graph, and the transitions are formed by replacing one of the edges at any vertex by a cyclically adjacent edge at the same vertex, is the result a medium?

The short answer: no, not generally. The longer answer:

( Read more... )

Ok, I think my idea from last time of using winding numbers is enough to patch Kaufmann's broken proof that his system of states of a knot diagram (equivalently, spanning trees of a plane-embedded graph, rooted at a vertex of the outer face) forms a lattice.

( Read more... )

So I've been reading through Louis Kaufmann's book Formal Knot Theory, which describes a lattice of "states" on four-regular plane-embedded (multi)graphs, and trying to understand it in different terms, as a structure of spanning trees and local changes from one spanning tree to another.

( Read more... )

So, at this point, while I still believe Kaufmann's claim that the rooted trees of a plane graph form a lattice, I think his proof is bogus. If they do form a distributive lattice, there is an underlying partial order (by Birkhoff) but it's not as simple as the one he describes. I think the elements of the order are pairs of a vertex in G and an integer, where the integer represents some kind of winding number, but I'm not sure of the details.

More later...

I'm far behind on my reading, so consider this as the first installment in my attempts to catch up.

( Efficient dual pairs of spanning trees )

( Robust de-anonymization of large datasets )

( Being first and ranking journals )

( Hinged dissections exist )

( Tribes of cubic partial cubes )