Formal knot theory, I: a bad proof
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.
A four-regular plane multigraph is the same thing as the medial graph of a plane graph without the 4-regularity restriction. To form the medial graph \(M(G)\) of a plane graph \(G\), place a vertex of \(M(G)\) at the midpoint of every edge of \(G\) and connect pairs of these medial vertices in \(M(G)\) whenever they belong to adjacent edges around the same face of \(G\). The faces of \(M(G)\) can be two-colored (more generally this is true for any plane graph with even degree at every vertex). The faces of one color in \(M(G)\) lie within the faces of \(G\), and the faces of the other color in \(M(G)\) surround the vertices of \(G\):
Kaufmann's states are formed by placing marks within each face of \(M(G)\). Two adjacent faces of \(M(G)\) are marked by stars; the remaining marks are placed near a vertex on each unstarred face of \(M(G)\), such that each vertex has exactly one mark near it. As Kaufmann shows, these marks correspond to a pair of interdigitating trees. If we return to the underlying graph \(G\), one of these trees is a spanning tree of \(G\), and one of these trees is a spanning tree of the planar dual of \(G\). These two spanning trees are rooted at the vertices corresponding to the starred faces of \(M(G)\), and the other marks in \(M(G)\) indicate the parent of each vertex in \(G\) or its dual. The dual spanning tree is determined once a spanning tree in \(G\) is selected (the dual spanning tree edges are the edges dual to edges of \(G\) that are not part of the primal spanning tree) so, less symmetrically, we can view a state as consisting of a choice of outer face of \(G\), a choice of a vertex on that outer face, and a spanning tree rooted at that vertex.
A rotation consists of finding two marks near the same edge of \(M(G)\) and replacing them with marks in the other two locations near that edge. In \(G\), this means: finding a spanning tree edge connecting some vertex \(v\) to its parent, removing it from the tree, and replacing it with an edge connecting \(v\) to a different parent, such that the edges to the old and new parents of \(v\) are adjacent on an interior face of \(G\) and such that the resulting graph remains a spanning tree. However, such a replacement is not allowed if it would cause a path in the dual tree to reverse its orientation. For instance, in the figures below, the center vertex is not allowed to choose the root as its new parent, even though that would form a valid tree, because it would reorient a dual path.
One can assign a direction to a rotation according to whether the replacement parent for \(v\) is clockwise or counterclockwise of its old parent. There are two extremal spanning trees for this assignment of directions, both of which can be found by a depth first search that prioritizes the edges at each vertex in the ordering given by the planar embedding, with the cyclic order at each vertex broken into a linear order by the edge connecting it to its DFS tree parent. Thus, these two extrema may be constructed in linear time.
So far, so good. But somewhere around page 50, I'm getting stuck. Kaufmann is claiming that there's a partial order on the set of possible rotations, or equivalently on the set of edges of \(M(G)\) (one can't rotate a mark clockwise from \(A\) to \(B\) until some other move has already put it at \(A\), and until the corresponding dual mark is in the corresponding position), and therefore that the states can be represented as lower sets of a partial order; by Birkhoff's representation theorem, the states form a distributive lattice in which the rotations from one state to another are the covering relations of the lattice. But there are two problems. First, and less importantly, he doesn't seem to show very carefully that every lower set actually forms a valid marking. But the real flaw is that this proof assumes that, in a sequence of clockwise rotations, the same rotation can happen only once. In Kaufmann's notation, in sequence of consistently-ordered rotations, he assumes that the same edge of \(M(G)\) can only be rotated once; in our notation of spanning trees in \(G\), he assumes that a spanning tree edge can only rotate around \(v\) from an old parent \(u\) to a new parent \(w\) once, and then forevermore is barred from repeating the same rotation. But that's not true. By making a more complex graph than the one described above, it is possible to make the two extremal trees spiral around many times before reaching the center, and therefore it's possible for the edge connecting the central vertex to its parent to rotate more than once around in the sequence of rotations connecting the two extremal trees. For instance, even in the five-vertex wheel shown below, the central vertex rotates six times going from one extreme tree to the other; two of the four possible rotations at that vertex are repeated. For larger graphs, the number of repetitions could be larger.
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.