This program finds matroids for a given plabic graph (see [1]). To use
it, run
./matroid-find path/to/file
where the file is of the following form:
[W]
a b c δ ε 当 ⑨
[B]
f g η ι foo bar
[E]
(a foo) (bar ε) (b c) (c δ) (ε 当)
(f ⑨) (η ι) (g bar)
(a BOUNDARY) (b BOUNDARY) (⑨ BOUNDARY)
In particular, there are three sections: for listing white nodes,
black nodes, and edges. The nodes must be whitespace-delimited, and
may be composed of any (non-whitespace) unicode characters except `[',
`]', `(', and `)'. The special node name `BOUNDARY' is reserved - an
edge between a node and BOUNDARY tells the program that that, in the
plabic graph, the connected node is a boundary node.
The program will interpret the file as a plabic graph, then attempt to
compute all possible sets of sink nodes for which a perfect
orientation is possible. This set of sets of nodes is the matroid of
the plabic graph.
On a more graph-theoretic level, the program attempts to assign
directions to the edges such that color-restrictions are satisified
(white nodes are connected to exactly one edge entering that node,
black nodes are connected to exactly one edge leaving that node). When
such a configuration is possible, the set of all nodes connected to a
boundary-ward arrow is the set of `sink nodes' for the graph, and is
an element in a special set. This program exhaustively finds all
elements of that special set.
The algorithm is vaguely as follows (recursive set-building is
implemented by applying a depth level to each edge, representing the
level at which its direction was decided).
function FIX_REQUIRED_EDGES: Graph x Set(Edges) -> Graph x Set(Edges) x Error
Let G = (V, E) be the graph
Let F ⊆ E be the set of edges which are fixed.
Let F' := F
For all v ∈ V {
If v.color is WHITE {
If some (a -> v) exists in F {
If a different (b -> v) exists in F {
Return (∅,∅,Contradiction)
}
For all (a,v) in E, add (v -> a) to F'
} else {
If no edges in E ∖ F contain v {
Return (∅,∅,Contradiction)
} otherwise, if there's exactly one (a,v) E ∖ F {
Add (a -> v) to F'
}
}
}
If v.color is BLACK {
Do the same as in the above case,
but the arrows point backwards.
}
}
return (G, F', ∅)
function HAS_A_PERFECT_ORDERING: Graph x Set(Edges) -> Boolean
Let G = (V, E) be the graph
Let F ⊆ E be the set of edges which are fixed.
If IS_CONTRADICTED(G, F) then return FALSE
If E = F {
Return TRUE
}
Let (a, b) be an edge in E ∖ F
Let (G', F', Error1) = FIX_REQUIRED_EDGES(G, F ∪ { (a -> b) })
If no Error and HAS_A_PERFECT_ORDERING(G', F') {
Return TRUE
}
Let (G', F', Error1) = FIX_REQUIRED_EDGES(G, F ∪ { (a <- b) })
If no Error and HAS_A_PERFECT_ORDERING(g', F')
Return TRUE
}
Return FALSE
function FIND_MATROIDS: Graph -> ∅
Let G = (V, E) be the graph
W := { v ∈ V | (v, BOUNDARY) ∈ E }
For all W' ∈ POWER_SET(W) {
F := { (w -> BOUNDARY) | w ∈ W'} ∪
{ (w <- BOUNDARY) | w ∉ W'}
If HAS_A_PERFECT_ORDERING(G, F) {
Print(W')
}
}
[1]: Alexander Postnikov, “Total positivity, Grassmannians, and
networks”, 2006. Preprint at <http://arxiv.org/abs/math/0609764>