README

   1 This program finds matroids for a given plabic graph (see [1]). To use
   2 it, run
   3
   4     ./matroid-find path/to/file
   5
   6 where the file is of the following form:
   7
   8     [W]
   9     a b c δ ε 当 ⑨
  10
  11     [B]
  12     f g η ι foo bar
  13
  14     [E]
  15     (a foo) (bar ε) (b c) (c δ) (ε 当)
  16     (f ⑨) (η ι) (g bar)
  17     (a BOUNDARY) (b BOUNDARY) (⑨ BOUNDARY)
  18
  19 In particular, there are three sections: for listing white nodes,
  20 black nodes, and edges. The nodes must be whitespace-delimited, and
  21 may be composed of any (non-whitespace) unicode characters except `[',
  22 `]', `(', and `)'. The special node name `BOUNDARY' is reserved - an
  23 edge between a node and BOUNDARY tells the program that that, in the
  24 plabic graph, the connected node is a boundary node.
  25
  26 The program will interpret the file as a plabic graph, then attempt to
  27 compute all possible sets of sink nodes for which a perfect
  28 orientation is possible.  This set of sets of nodes is the matroid of
  29 the plabic graph.
  30
  31 On a more graph-theoretic level, the program attempts to assign
  32 directions to the edges such that color-restrictions are satisified
  33 (white nodes are connected to exactly one edge entering that node,
  34 black nodes are connected to exactly one edge leaving that node). When
  35 such a configuration is possible, the set of all nodes connected to a
  36 boundary-ward arrow is the set of `sink nodes' for the graph, and is
  37 an element in a special set. This program exhaustively finds all
  38 elements of that special set.
  39
  40 The algorithm is vaguely as follows (recursive set-building is
  41 implemented by applying a depth level to each edge, representing the
  42 level at which its direction was decided).
  43
  44 function FIX_REQUIRED_EDGES: Graph x Set(Edges) -> Graph x Set(Edges) x Error
  45     Let G = (V, E) be the graph
  46     Let F ⊆ E be the set of edges which are fixed.
  47     Let F' := F
  48     For all v ∈ V {
  49         If v.color is WHITE {
  50             If some (a -> v) exists in F {
  51                 If a different (b -> v) exists in F {
  52                     Return (∅,∅,Contradiction)
  53                 }
  54                 For all (a,v) in E, add (v -> a) to F'
  55             } else {
  56                If no edges in E ∖ F contain v {
  57                    Return (∅,∅,Contradiction)
  58                } otherwise, if there's exactly one (a,v) E ∖ F {
  59                    Add (a -> v) to F'
  60                }
  61             }
  62         }
  63         If v.color is BLACK {
  64             Do the same as in the above case,
  65             but the arrows point backwards.
  66         }
  67     }
  68     return (G, F', ∅)
  69
  70 function HAS_A_PERFECT_ORDERING: Graph x Set(Edges) -> Boolean
  71     Let G = (V, E) be the graph
  72     Let F ⊆ E be the set of edges which are fixed.
  73     If IS_CONTRADICTED(G, F) then return FALSE
  74     If E = F {
  75         Return TRUE
  76     }
  77
  78     Let (a, b) be an edge in E ∖ F
  79
  80     Let (G', F', Error1) = FIX_REQUIRED_EDGES(G, F ∪ { (a -> b) })
  81     If no Error and HAS_A_PERFECT_ORDERING(G', F') {
  82         Return TRUE
  83     }
  84
  85     Let (G', F', Error1) = FIX_REQUIRED_EDGES(G, F ∪ { (a <- b) })
  86     If no Error and HAS_A_PERFECT_ORDERING(g', F')
  87         Return TRUE
  88     }
  89
  90     Return FALSE
  91
  92 function FIND_MATROIDS: Graph -> ∅
  93     Let G = (V, E) be the graph
  94     W := { v ∈ V | (v, BOUNDARY) ∈ E }
  95
  96     For all W' ∈ POWER_SET(W) {
  97         F := { (w -> BOUNDARY) | w ∈ W'} ∪
  98              { (w <- BOUNDARY) | w ∉ W'}
  99         If HAS_A_PERFECT_ORDERING(G, F) {
 100             Print(W')
 101         }
 102     }
 103
 104 [1]: Alexander Postnikov, “Total positivity, Grassmannians, and
 105      networks”, 2006. Preprint at <http://arxiv.org/abs/math/0609764>