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 -enum -compact
  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 Every plabic graph admits many, many networks. Some (maybe none) of
  46 those 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 set of collections of sink vertices which admit a perfectly
  56 oriented network: i.e. fixing these boundary vertices as sinks, and
  57 the other boundary vertices as sources, allows a choice of edge
  58 directions such that the resulting plabic network is perfectly
  59 oriented. For more information, see Postnikov's paper.
  60 .Pp
  61 .Rs
  62 .%A Alexander Postnikov
  63 .%D 2006
  64 .%T Total Positivity, Grassmannians, and Networks
  65 .%O Preprint at http://arxiv.org/abs/math/0609764
  66 .Re
  67 .Sh FILES
  68 The
  69 .Nm
  70 program must read a description of a plabic graph from a file. The
  71 file is of the following form:
  72 .Pp
  73 .Dl [W]
  74 .Dl Ar name Ar name Ar name Ar ...
  75 .Dl Ar name Ar name Ar name Ar ...
  76 .Dl Ar ...
  77 .Dl
  78 .Dl [B]
  79 .Dl Ar name Ar name Ar name Ar ...
  80 .Dl
  81 .Dl [E]
  82 .Dl Po Ar name Ar name Pc  Po Ar name Ar name Pc Ar ...
  83 .Pp
  84 where each
  85 .Ar name
  86 is the name of a vertex: a collection of non-whitespace characters
  87 .Pq unicode is okay
  88 that are not
  89 .Ql \&[ ,
  90 .Ql \&] ,
  91 .Ql \&( ,
  92 or
  93 .Ql \&) .
  94 Those vertices listed following
  95 .Ql [W]
  96 are colored white, those following
  97 .Ql [B]
  98 are colored black. No duplication is allowed. Edges are listed
  99 following the
 100 .Ql [E]
 101 marker, and must be either between two
 102 .Ql distinct
 103 vertices or between a vertex and the special string
 104 .Ql BOUNDARY ,
 105 which is not allowed as a vertex name. An edge between
 106 .Ar v
 107 and
 108 .Ar BOUNDARY
 109 marks
 110 .Ar v
 111 as a boundary vertex.