matroid-finder.1

   1 .Dd 2016-06-01
   2 .Dt MATROID-FINDER 1
   3 .Os
   4 .Sh NAME
   5 .Nm matroid-finder
   6 .Nd finds matroids of plabic graphs
   7 .Sh SYNOPSIS
   8 .Nm
   9 .Ar input-file
  10 .Sh DESCRIPTION
  11 A
  12 .Em plabic ,
  13 or
  14 .Ql planar, bicolored
  15 graph, is a collection of vertices, undirected edges, and a color
  16 associated to each vertex: either black or white. Edges may either be
  17 between two vertices, or from some vertex to a point on
  18 .Ql the boundary
  19 of the graph: a circle enclosing the entire graph. The edges cannot
  20 cross
  21 .Pq this is what it means to be Em planar
  22 , and the graph need not be connected. A vertex can only be
  23 adjacent to one boundary edge: such vertices are called
  24 .Ql boundary vertices
  25 .Pp
  26 We may consider turning a plabic graph from an undirected graph into a
  27 directed one, simply by assigning directions to each edge.  This turns
  28 the plabic graph into a
  29 .Em network.
  30 .Pp
  31 A network associated to a plabic graph is
  32 .Em perfectly oriented
  33 if the following conditions are satisfied.
  34 .Bl -bullet
  35 .It
  36 For every white vertex, exactly one edge points
  37 .Em towards
  38 it.
  39 .It
  40 For every black vertex, exactly one edge points
  41 .Em away from
  42 it.
  43 .El
  44 .Pp
  45 Most plabic graphs admit many networks. Some (maybe none) of those
  46 networks are perfectly oriented. For a number of interesting
  47 properties, it turns out that all that matters is the directions of
  48 the boundary edges. A boundary vertex whose boundary edge points away
  49 from it
  50 .Pq towards the boundary
  51 is called a
  52 .Em sink vertex .
  53 A boundary vertex whose boundary edge points towards it is called a
  54 .Em source vertex .
  55 The
  56 .Em matroid
  57 of a plabic graph is the set of collections of sink vertices which
  58 admit a perfectly oriented network: i.e. fixing these boundary
  59 vertices as sinks, and the other boundary vertices as sources, allows
  60 a choice of edge directions such that the resulting plabic network is
  61 perfectly oriented. For more information, see Postnikov's paper.
  62 .Pp
  63 .Rs
  64 .%A Alexander Postnikov
  65 .%D 2006
  66 .%T Total Positivity, Grassmannians, and Networks
  67 .%O Preprint at http://arxiv.org/abs/math/0609764
  68 .Re
  69 .Sh FILES
  70 The
  71 .Nm
  72 program must read a description of a plabic graph from a file. The
  73 file is of the following form:
  74 .Pp
  75 .Dl [W]
  76 .Dl Ar name Ar name Ar name Ar ...
  77 .Dl Ar name Ar name Ar name Ar ...
  78 .Dl Ar ...
  79 .Dl
  80 .Dl [B]
  81 .Dl Ar name Ar name Ar name Ar ...
  82 .Dl
  83 .Dl [E]
  84 .Dl Po Ar name Ar name Pc  Po Ar name Ar name Pc Ar ...
  85 .Pp
  86 where each
  87 .Ar name
  88 is the name of a vertex: a collection of non-whitespace characters
  89 .Pq unicode is okay
  90 that are not
  91 .Ql \&[ ,
  92 .Ql \&] ,
  93 .Ql \&( ,
  94 or
  95 .Ql \&) .
  96 Those vertices listed following
  97 .Ql [W]
  98 are colored white, those following
  99 .Ql [B]
 100 are colored black. No duplication is allowed. Edges are listed
 101 following the
 102 .Ql [E]
 103 marker, and must be either between two
 104 .Ql distinct
 105 vertices or between a vertex and the special string
 106 .Ql BOUNDARY ,
 107 which is not allowed as a vertex name. An edge between
 108 .Ar v
 109 and
 110 .Ar BOUNDARY
 111 marks
 112 .Ar v
 113 as a boundary vertex.