%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{91}
\bibliography{bibliographie}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\usepackage{lipsum}
\usepackage{verbatim}



\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{property}[theorem]{Property}
%\newtheorem{otherthm}{Theorem}[section]
\newtheorem{convention}[theorem]{Convention}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exercice}[theorem]{Exercise}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\newcommand{\N}{\mathbb{N}}
\renewcommand{\S}{\mathbb{S}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\cc}{\mathbb{C}}
\newcommand{\Ga}{\Gamma}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\cp}{\mathbb{CP}^2}
\renewcommand{\k}{\mathbcal{k}}

\newcommand{\ind}[1]{\mathbf{1}_{\left\{#1\right\}}}
\newcommand{\indset}[1]{\mathbf{1}_{#1}}
\newcommand{\floor}[1]{{\left\lfloor #1 \right\rfloor}}
\newcommand{\ceil}[1]{{\left\lceil #1 \right\rceil}}
\newcommand{\norme}[1]{{\left\Vert #1 \right\Vert}}
\DeclareMathOperator{\E}{\mathbf{E}}
\renewcommand{\P}{\mathbf{P}}
\DeclareMathOperator{\Var}{\mathbf{V}\mathrm{ar}}
\newcommand{\crochet}[1]{{\langle #1 \rangle}}
\newcommand{\e}{\mathbf{e}}
\renewcommand{\v}{\mathbf{v}}
\newcommand{\vtilde}{\tilde{\mathbf{v}}}
\newcommand{\Rvec}{\mathbf{R}}
\newcommand{\W}{\mathbb{W}}

\renewcommand{\e}{\mathrm{e}}
\newcommand{\dx}{\mathrm{d}x}
\newcommand{\eq}{\mathrm{eq}}
\newcommand{\egaldistr}{\overset{(d)}{=}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\row}{\mathrm{row}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\Rel}{\mathrm{Rel}}
\newcommand{\sgn}{\mathrm{sgn}}



%% define your title in the usual way
\title{Vector-relation configurations and plabic graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details

\author[Niklas Affolter, Max Glick, Pavlo Pylyavskyy, and Sanjay Ramassamy]{Niklas Affolter\thanks{%\href{mailto:blah}{blah}. 
Supported by DFG SFB/Transregio 109 ``Discretization in Geometry and Dynamics''}\addressmark{1}, Max Glick\thanks{\href{mailto:max.i.glick@gmail.com}{max.i.glick@gmail.com}.}\addressmark{2}, Pavlo Pylyavskyy\thanks{%\href{mailto:blah}{blah}. 
Partially supported by NSF grants DMS--1148634 and DMS--1351590.}\addressmark{3},\\ \and Sanjay Ramassamy\thanks{%\href{mailto:blah}{blah}. 
Partially supported by the ANR-18-CE40-0033 project DIMERS.}\addressmark{4}}



%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Technische Universit\"at Berlin, Institute of Mathematics, Berlin, Germany \\ 
	\addressmark{2}Department of Mathematics, The Ohio State University, Columbus, OH, USA \\
	\addressmark{3}Department of Mathematics, University of Minnesota, Minneapolis, MN, USA \\
	\addressmark{4}D\'epartement de math\'ematiques et applications, \'Ecole normale sup\'erieure, CNRS, Paris, France}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study a simple geometric model for local transformations of bipartite graphs.  The state consists of a choice of a vector at each white vertex made in such a way that the vectors neighboring each black vertex satisfy a linear relation.  Evolution for different choices of the graph coincides with many notable dynamical systems including the pentagram map, $Q$-nets, and discrete Darboux maps.  On the other hand, for plabic graphs we prove unique extendability of a configuration from the boundary to the interior, an elegant illustration of the fact that Postnikov's boundary measurement map is invertible.  In all cases there is a cluster algebra operating in the background, resolving the open question for $Q$-nets of whether such a structure exists.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Pentagram map, plabic graphs, dimer model}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{bibliographie.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction} \label{sec:intro}
The dynamics of local transformations on weighted networks plays a central role in a number of settings within algebra, combinatorics, and mathematical physics.  In the context of the dimer model on a torus, these local moves give rise to the discrete cluster integrable systems of Goncharov and Kenyon \cite{GK}.  Meanwhile, for plabic graphs in a disk, Postnikov transformations relate different parametrizations of positroid cells \cite{Pos06} which in turn define a stratification of the totally non-negative Grassmannian.

The dimer model also manifests itself in many geometrically defined dynamical systems.  We focus on projective geometry and draw our initial motivation from the pentagram map.  The pentagram map was defined by Schwartz \cite{S92} and related to coefficient-type cluster algebra dynamics in \cite{G11}.  Gekhtman, Shapiro, Tabachnikov, and Vainshtein  \cite{GSTV12,GSTV16} placed the pentagram map and certain generalizations in the context of weighted networks. Although considerable work in various directions of the subject has been undertaken, most relevant to our work is a further generalization termed $Y$-meshes \cite{GP16}.

We propose a simple but versatile geometric model for the space of edge weights of any bipartite graph modulo gauge equivalence.  The induced dynamics of local transformations includes in special cases pentagram maps, $Q$-nets, and discrete Darboux maps.  This common generalization resolves a long standing question of how the pentagram map and $Q$-nets relate.  Moreover, our systems come with a cluster dynamics, which is new in the $Q$-net case.  Lastly, in the setting of plabic graphs we define a geometric version of the boundary measurement map and its inverse.  In this language, properties of the boundary measurement map imply unique solvability of a certain family of geometric realization problems.


Let $G$ be a planar bipartite graph with vertex set $B \cup W$.  For $b\in B$ let $N(b) \subseteq W$ denotes its set of neighbors.  Fix a vector space $V$.  A \emph{circuit} is a subset $S \subseteq V$ such that $S$ is linearly dependent but each of its proper subsets is linearly independent.  

\begin{definition} \label{def:vr}
A \emph{vector-relation configuration} on $G$ consists of choices of 
\begin{itemize}
\item a nonzero vector $v_w \in V$ for each $w \in W$ and
\item a non-trivial linear relation $R_b$ among the vectors $\{v_w : w \in N(b)\}$ for each $b \in B$.
\end{itemize}
In particular, each set $\{v_w : w \in N(b)\}$ must be linearly dependent.  If each set $\{v_w : w \in N(b)\}$ is a circuit, say the configuration satisfies the \emph{circuit condition}.  
\end{definition}

\begin{definition} \label{def:gauge}
Consider a vector-relation configuration on a graph $G$ as above and suppose $\lambda \neq 0$.  The \emph{gauge transformation} by $\lambda$ at a black vertex $b \in B$ scales the relation $R_b$ by $\lambda$ (and keeps all other vectors and relations the same).  The \emph{gauge transformation} by $\lambda$ at a white vertex $w \in W$ scales $v_w$ by $1/\lambda$ and scales the coefficient of $v_w$ by $\lambda$ in each relation in which it appears to compensate.  Two vector-relation configurations are called \emph{gauge equivalent} if they are related by a sequence of gauge transformations.
\end{definition}

Gauge equivalence classes of vector-relation configurations serve as our main object of study.  For the remainder of the introduction, we define both local transformations and a boundary measurement type map for such configurations, and present our main results.

\subsection{Local transformations}
Goncharov and Kenyon \cite{GK} study line bundles with connection on bipartite graphs.  This model amounts to a choice of edge weights modulo a notion of gauge equivalence.  They also define local transformations of the graph and edge weights which are closely related to Postnikov moves \cite{Pos06} in weighted directed networks.  

Let $G = (B \cup W, E)$ be a planar bipartite graph.  Let $(\v,\Rvec)$ be a vector-relation configuration on $G$.  We can define edge weights
\begin{displaymath}
\wt(\overline{bw}) = \pm K_{bw}
\end{displaymath}
where $K_{bw}$ is the coefficient of $v_w$ in $R_b$ and the signs satisfy the Kasteleyn condition, namely the product of signs on edges around each $2m$-gon face equals $(-1)^{m-1}$.  A choice of Kasteleyn signs always exists and, in the plane, any two such choices are gauge equivalent (see e.g. \cite{Ken09}).

\begin{theorem} \label{thm:moves}
The above associates a line bundle with connection on $G$ to each gauge class of vector-relation configurations satisfying the circuit condition.  Moreover, the classical local transformations can be implemented on the vector-relation level via local geometric rules.
\end{theorem}

In \cref{sec:config}, we define these local rules and also give geometric definitions of face weights which are the main gauge-invariant coordinates.  We also explain the sense in which our model is a common generalization of the pentagram map and $Q$-nets.

\subsection{Configurations on plabic graphs} \label{subsec:plabic}
Plabic graphs are a family of finite planar graphs widely used in the study of positroids and the totally non-negative Grassmannian.  Restricted to this case, our model provides a new take on plabic graphs and much of the surrounding theory.

A \emph{plabic graph} is a finite planar graph $G=(B \cup W, E)$ embedded in a disk with the vertices all colored black or white.  We assume throughout that $G$ is in fact bipartite and that all of its boundary vertices are colored white.  An \emph{almost perfect matching} of $G$ is a matching that uses all internal vertices (and some boundary vertices).  Assume always that $G$ has at least one almost perfect matching.

Fix for the moment a plabic graph $G=(B \cup W, E)$.  Let $M = |B|$, $N=|W|$, and let $n$ be the number of boundary vertices.  As all boundary vertices are white that leaves $N-n$ internal white vertices.  Number the elements of $B$ and $W$ respectively $1$ through $M$ and $1$ through $N$  in such a way that the boundary (white) vertices are numbered $1$ through $n$ in clockwise order.  We will sometimes use these numbers in place of the vertices, e.g. writing $v_i$ for the vector of a configuration at the white vertex numbered $i$.  Let $k = N-M$.  Each almost perfect matching uses exactly $n-k$ boundary vertices.

We make some modifications to our model to better cater to plabic graphs and related geometry.  First, the natural ambient dimension is $k=N-M$ so we simply fix as our vector space $V = \mathbb{C}^k$.  We also require that the boundary vertices $v_1,\ldots, v_n$ span $V$.  The main result given these assumptions, which in isolation is rather striking, is that a configuration is uniquely determined up to gauge by its boundary vectors.  Moreover, the boundary vectors can be viewed as columns of a $k \times n$ matrix $[v_1 \cdots v_n]$ and the subset of the Grassmannian arising this way is dense in the associated positroid variety.

\begin{theorem} \label{thm:plabic}
Fix a plabic graph $G$ with all the preceding conventions and notation.
\begin{enumerate}
\item If $(\v, \Rvec)$ is a vector-relation configuration on $G$ satisfying the circuit condition then $A = [v_1 \cdots v_n]$ lies in the positroid variety $\Pi_{\mathcal{M}}$ where $\mathcal{M}$ is the positroid of $G$.
\item Suppose $G$ is reduced.  For generic $A \in \Pi_{\mathcal{M}}$, the columns $v_1,\ldots, v_n$ of $A$ can be extended to a vector-relation configuration on $G$ that is unique up to gauge at internal vertices.  In particular, each internal vector is determined up to scale.
\end{enumerate}
\end{theorem}

In \cref{sec:background} we review the definitions of the positroid $\mathcal{M}$, the variety $\Pi_{\mathcal{M}} \subseteq Gr_{k,n}$, and the reducedness condition for plabic graphs.


\begin{example} \label{ex:gr36}
Consider the plabic graph $G$ in \cref{fig:gr36}.  It has $k=3$ and $n=6$.  In fact, the associated positroid is the uniform matroid, meaning all $3$ element subsets of $\{1,\ldots, 6\}$ are included.  So the positroid variety is the whole Grassmannian $Gr_{3,6}$.  In short, the boundary vectors $v_1,\ldots v_6 \in \mathbb{C}^3$ of a configuration can be generic.

Now suppose $v_1,\ldots v_6 \in \mathbb{C}^3$ are given and consider the possibilities for the internal vector $u$.  The lower black vertex forces $u,v_1,v_2$ to be dependent while the top black vertex forces $u,v_4,v_5$ to be dependent.  If the $v_i$ are generic then $u$ must lie on the line of intersection of the planes $\langle v_1,v_2 \rangle$ and $\langle v_4, v_5 \rangle$.  Hence $u$ is determined up to scale.  The other two black vertices have degree $4$.  It is always possible to find a linear relation among $4$ vectors in $\mathbb{C}^3$, so there are no added conditions imposed on $u$.
\end{example}

\begin{figure}
\centering
\includegraphics[height=2.5in]{config36.eps}
\caption{A plabic graph corresponding to the open cell in $Gr(3,6)$}
\label{fig:gr36}
\end{figure}

\subsection{Relation to previous work} Our model of vector-relation configurations has substantial precedent in the literature.  In fact, a main selling point of our specific formulation is that it is versatile enough to tie into previously studied ideas in a variety of areas.  We outline some of the relevant previous work here for the interested reader's convenience.

In the plabic graph setting, Lam's \emph{relation space} \cite[Section 14]{LamCDM} is in a sense dual to our model.  
In light of this connection, Lam's main result \cite[Theorem 14.6]{LamCDM} demonstrates that the operation of boundary restriction as in our \cref{thm:plabic} agrees up to sign with the boundary measurement map \cite{Pos06}.  Our only claims to originality in \cref{thm:plabic} are the elegance and the elementary geometric nature both of the formulation and of our proofs.  Another related model is provided by Postnikov \cite{Pos18}.  Both \cite[Section 14]{LamCDM} and \cite{Pos18} are attempts to put on more mathematical footing on-shell diagrams \cite{Nima}, and in fact physicists have informed us that vector-relation configurations are one way they think about said diagrams.

In the case of the dimer model on the torus, special cases and other hints of vector-relation configurations appear in the following settings: higher pentagram maps \cite{GSTV12,GSTV16}, discrete differential geometry \cite{BS}, and the inverse spectral transform \cite{KO,F15}.  We close this section by noting that the full version \cite{AGPR} of this extended abstract contains full proofs of all results as well as investigations in a number of related directions.


\section{Vector-relation configurations} \label{sec:config}
In this section we develop the theory of vector-relation configurations on general planar bipartite graphs as in \cref{def:vr,def:gauge}.  To that end, let $G = (B \cup W, E)$ be a planar bipartite graph.  We will denote a vector-relation configuration on $G$ by $(\v,\Rvec)$ (or sometimes just $\v$ for short) where $\v = (v_w)_{w \in W}$ and $\Rvec = (R_b)_{b \in B}$.

For each $w \in W$, let $P_w$ denote the projection of $v_w \in V$ to the corresponding projective space $\mathbb{P}V$.

\begin{proposition}
If $(\v,\Rvec)$ satisfies the circuit condition then the points $(P_w)_{w \in W}$ uniquely determine the gauge class of the configuration.
\end{proposition}

We work on the level of the point configurations $(P_w)_{w \in W}$ for the remainder of this section.  They are characterized by the property that for each $b \in B$ the set $\{P_w : w \in N(b)\}$ is a circuit in projective space (e.g. $4$ coplanar points, no $3$ of which are collinear).  Note that for any partition of a circuit into two subsets, there is a unique point on the intersection of the affine hulls of the subsets.  Fix $b \in B$.  Let $F$ be a face containing $b$ and let $w_1,w_2$ be the neighbors of $b$ along $F$.  
Define $P(F,b)$ to be the point
\begin{equation} \label{eq:PFb}
P(F,b) = \langle P_{w_1}, P_{w_2} \rangle \cap \langle \{P_w : w \in N(b) \setminus \{w_1,w_2\}\} \rangle
\end{equation}
where $\langle \cdot \rangle$ denotes an affine span.

\cref{fig:moves} depicts the local transformations that we consider on bipartite graphs and sets notation for some of the graphs' vertices.  We extend each transformation to a mapping of point configurations.  The first move is \emph{urban renewal} which operates on a quadrilateral face $F$ of the original graph.  Define points at the new white vertices $w_1',w_2'$ to be $P_{w_1'} = P(F,b_1)$ and $P_{w_2'} = P(F,b_2)$.  The other two moves split a vertex into two new vertices of the same color, which are then attached by a new degree two vertex of the opposite color.  If the vertex being split is a white vertex $w$, them put the same point $P_{w_1'}=P_{w_2'} = P_w$ at each new white vertex.  Lastly, if the vertex being split is black there is a new degree two white vertex $w'$.  Put 
\begin{displaymath}
P_{w'} = \langle P_{w_1}, \ldots, P_{w_k} \rangle \cap \langle P_{w_{k+1}} \ldots P_{w_{k+l}} \rangle.
\end{displaymath}

\begin{figure}
\centering
\includegraphics[height=4in]{moves.eps}
\caption{Combinatorial local moves on planar bipartite graphs.}
\label{fig:moves}
\end{figure}


\begin{proposition}
The above definitions yield valid point configurations on the graph resulting from each move.  
\end{proposition}

It is a direct verification that the dynamics on the points $P_w$ correspond to classical local transformations on edge weights as claimed by \cref{thm:moves}.

For a line bundle with connection on $G$, the basic gauge invariant functions are the \emph{monodromies} around individual faces.  These face weights evolve under local transformations via $Y$-pattern dynamics \cite{FZ} of the cluster algebra associated to the dual quiver.  As such, the same formulas apply to our geometrically defined systems.  Moreover, the face weights have simple projectively invariant formulas.


Suppose points $P_{1},\ldots, P_{2k}$ in an affine space are given with the triples $\{P_1,P_2,P_3\}$, $\{P_3,P_4,P_5\}$, \ldots, $\{P_{2k-1},P_{2k},P_1\}$ all collinear.  The \emph{multi-ratio} (called a \emph{cross ratio} for $k=2$ and a \emph{triple ratio} for $k=3$) of the points is
\begin{displaymath}
[P_1,\ldots, P_{2k}] = \frac{P_1-P_2}{P_2-P_3} \frac{P_3-P_4}{P_4-P_5} \cdots \frac{P_{2k-1}-P_{2k}}{P_{2k}-P_1}.
\end{displaymath}
Each individual fraction involves $3$ points on a line and is interpreted as a ratio of signed distances.

\begin{proposition} \label{prop:faceweights}
Let $F$ be a face with boundary cycle $w_1, b_1, w_2, b_2, \ldots, w_m, b_m$ in clockwise order.  In terms of the points $P_w$, the face weight of $F$ equals
\begin{displaymath}
Y_F = (-1)^{m-1}[P_{w_1}, P(F,b_1), P_{w_2}, P(F,b_2), \ldots, P_{w_m}, P(F,b_m)]^{-1}.
\end{displaymath}

\end{proposition}

\begin{example}
The \emph{pentagram map} \cite{S92} inputs a polygon in the plane with vertices $A_i$ and outputs the polygon with vertices $B_i = \langle A_{i-1}, A_{i+1} \rangle \cap \langle A_i, A_{i+2} \rangle$.  Let $G$ be an infinite square grid and associate an $A_i$ to each white vertex of $G$ in the manner suggested by \cref{fig:penta}.  The two new points produced by urban renewal at $F$ are precisely $B_3$ and $B_4$.  In fact, urban renewal at half the faces (in a checkerboard pattern) followed by some degree $2$ vertex removals results in a full application of the pentagram map.
\end{example}

\begin{figure}
\centering
\includegraphics[height=2in]{pentaFPSAC.eps}
\caption{A portion of the bipartite graph whose vector-relation dynamics coincide with the pentagram map.}
\label{fig:penta}
\end{figure}

\begin{example}
A $Q$-net \cite{DS} is a map from $\mathbb{Z}^3$ to $3$-space such that each primitive square maps to four coplanar points.  Sufficient initial data for a $Q$-net lives on a so-called stepped surface which when projected to a plane looks like an infinite tiling by regular rhombi.  A point of the $Q$-net lives at each vertex of the tiling and the four points associated to each rhombus are coplanar.  This setup can be modeled by a bipartite graph $G$ with a white vertex at each vertex of the tiling, a black vertex in the center of each rhombus, and edges connecting them in the natural way.  A certain sequence of four urban renewals studied in \cite{KLRR} realizes one step of $Q$-net dynamics which on the tiling level amounts to flipping three rhombi inside a regular hexagon.
\end{example}


\begin{comment}
\section{Examples} \label{sec:examples}
In this section, we consider several projective geometric systems from the literature, and explain how they fit in our framework.  For each we identify the appropriate bipartite graph as well as the sequence of local transformations realizing the system.  In some cases we also explicitly work out the associated dynamics on the face weights.

\subsection{The pentagram family}
\begin{example}
The Laplace-Darboux system \cite{D97} operates on a $2$-dimensional array of points in $\mathbb{P}^3$ for which the points of each primitive square are coplanar.  It is convenient to index the points as $P_{i,j}$ for $i,j \in \mathbb{Z}$ with $i+j$ even.  The centers of the squares are then $(i,j)$ with $i+j$ odd so the condition is
\begin{equation} \label{eq:laplaceCond}
P_{i,j-1}, P_{i-1,j}, P_{i+1,j}, P_{i,j+1} \textrm{ coplanar for $i+j$ odd}.
\end{equation}
The system produces a new array of points $Q_{i,j}$ for $i+j$ odd defined by
\begin{displaymath}
Q_{i,j} = \langle P_{i,j-1}, P_{i+1,j} \rangle \cap \langle P_{i-1,j}, P_{i,j+1}  \rangle.
\end{displaymath}

To state Laplace-Darboux dynamics in our language take the infinite square grid graph $G = (\mathbb{Z}^2, E)$, which is bipartite with white vertices being those $(i,j)$ with $i+j$ even.  Place the points $P_{i,j}$ above at the white vertices.  For each black vertex $(i,j)$ with $i+j$ odd, the circuit condition says that the $4$ neighboring points should be coplanar, which is precisely \eqref{eq:laplaceCond}.

To evolve the system, perform urban renewal at each face whose upper left corner is black.  \cref{fig:laplace} shows a local picture.  Taking $F,b$ as in the picture, one of the new points is
\begin{displaymath}
P(F,b) = \langle P_{2,0}, P_{3,1} \rangle \cap \langle P_{1,1}, P_{2,2} \rangle = Q_{2,1}.
\end{displaymath}
Eliminating all degree $2$ vertices in the resulting picture recovers the square lattice except with the colors of vertices reversed.  The surviving points are precisely the $Q_{i,j}$.
\end{example}

\begin{figure}
\centering
\includegraphics[height=2in]{laplace.eps}
\caption{The local transformations which, when followed by degree $2$ vertex removals, realize Laplace-Darboux dynamics.}
\label{fig:laplace}
\end{figure}
 


\begin{example}
The pentagram map inputs a polygon in the plane with vertices $A_i$ for $i \in \mathbb{Z}$ and outputs the polygon with vertices 
\begin{displaymath}
B_i = \langle A_{i-1}, A_{i+1} \rangle \cap \langle A_{i}, A_{i+2} \rangle.
\end{displaymath}
This operation can be seen as a reduction of Laplace-Darboux dynamics.  Indeed, one can check that letting
\begin{align*}
P_{i,j} &= A_{(i+3j)/2}, \textrm{ $i+j$ even} \\
Q_{i,j} &= B_{(i+3j-1)/2}, \textrm{ $i+j$ odd}
\end{align*}
gives an input-output pair for Laplace-Darboux.  Note that $P_{i,j} = P_{i-3,j+1}$ and moreover if $A$ is a closed $n$-gon meaning $A_{i+n} = A_i$ then $P_{i,j} = P_{i+2n,j}$.

As the bipartite graph for Laplace-Darboux was the square grid on $\mathbb{Z}^2$, the correct choice for the pentagram map is its quotient of this graph by the lattice generated by $(-3,1)$ and $(2n,0)$.  This is a bipartite graph on a torus.  Point $A_i$ live at the vertex (equal to the class of) $(2i,0)$.  The relations are of the form $A_{i-1}, A_i, A_{i+1}, A_{i+2}$ coplanar which explains why the whole configuration must be in a plane.  Finally, the local transformations take the same form as for Laplace-Darboux.

The face weights of a polygon are precisely the $y$-parameters as defined in \cite{G11}.  As an example, \cref{fig:penta} gives a portion of the bipartite graph.  Applying \cref{prop:faceweights}, the variable at the face labeled $F$ is
\begin{displaymath}
Y_F = -[A_3, \langle A_3, A_4 \rangle \cap \langle A_1, A_2 \rangle, A_4, \langle A_3, A_4 \rangle \cap \langle A_5, A_6 \rangle]^{-1}.
\end{displaymath}

Although this algebraic formulation of the pentagram map was known, there may be other insights to be gained from the vector-relation perspective.  For instance, if nearby vertices of a polygon come together it creates a singularity for the pentagram map dynamics.  Keeping track of the coefficients of the relation satisfied by the points as they come together would be one way to try to control the behavior through the singularity.
\end{example}

\begin{figure}
\centering
\includegraphics[height=2in]{penta.eps}
\caption{A portion of the bipartite graph whose vector-relation dynamics coincide with the pentagram map.}
\label{fig:penta}
\end{figure}

\begin{example}
Different ways of putting the square grid graph on the torus produce different interesting systems.  The higher pentagram map of Gekhtman et al. is obtained by working in $\mathbb{RP}^d$ and identifying $(i,j)$ with $(i-d-1,j+d-1)$.  Indeed, the $(-i,i)$ form a set of representatives of the white vertices.  Placing a point $P_i$ at each $(-i,i)$, the neighbors of a given black vertex are labeled by $P_i, P_{i+1}, P_{i+d}, P_{i+d+1}$.  The condition that such four-tuples be coplanar is called the corrugated property and the resulting dynamics produces points
\begin{displaymath}
\langle P_i, P_{i+d} \rangle \cap \langle P_{i+1}, P_{i+d+1} \rangle
\end{displaymath}
as in the higher pentagram map.
\end{example}

\begin{example}
The left of \cref{fig:spiral} depicts one step of a certain pentagram spiral system.  The input is a \emph{seed} consisting of five points $A_1,\ldots, A_5$ with $A_5$ lying on the line through $A_1$ and $A_4$.  The output is a new seed $A_2,\ldots, A_6$ with $A_6 = \langle A_1, A_3 \rangle \cap \langle A_2, A_5 \rangle$.  If iterated the result is a polygonal curve that spirals inwards indefinitely.

\begin{figure}
\centering
\includegraphics[height=2in]{spiral.eps}
\caption{One step of a system that produces a pentagram spiral (left) along with the associated bipartite graph (right).}
\label{fig:spiral}
\end{figure}

The right of \cref{fig:spiral} shows a bipartite graph whose vector-relation dynamics capture this system.  As with the pentagram map on hexagons, the vertex set of the graph $G$ is $\mathbb{Z}^2$ modded out by the lattice generated by $(-3,1)$ and $(12,0)$.  However, $G$ does not include all of the edges from the square grid.  The figure shows exactly one copy of each edge and each black vertex, while the repeats among white vertices help to visualize how the picture repeats when lifted to $\mathbb{Z}^2$.

Place points $A_i$ for $i=1,\ldots, 6$ at the white vertices.  There are three degree $4$ black vertices which give conditions that $\{A_1,A_2,A_3,A_4\}$, $\{A_2,A_3,A_4,A_5\}$, and $\{A_3,A_4,A_5,A_6\}$ are coplanar.  As such, all six points are on a common plane.  There are also three degree $3$ black vertices implying that the triples $\{A_1,A_4,A_5\}$, $\{A_1,A_3,A_6\}$, and $\{A_2,A_5,A_6\}$ are collinear.  These match the defining conditions of the six points in the left picture.  In short, being a configuration on $G$ is equivalent to being a union of two consecutive seeds of the pentagram spiral.

We give a quick description of how to realize spiral dynamics.  There is a quadrilateral face of $G$ containing white vertices $1$ and $3$.  Urban renewal at this face followed by a degree $2$ vertex removal will produce a graph isomorphic to $G$.  The points $A_2,\ldots, A_6$ will remain and there will also be a new point $A_7 = \langle A_1, A_3 \rangle \cap \langle A_2, A_4 \rangle$, which is the next point on the spiral.  So the dynamics on the graph are equivalent to the spiral map, with the only discrepancy being that the former keeps track of six consecutive points at each time instead of five.

The graph $G$ is a special case of the dual graph to a Gale-Robinson quiver.  It is likely that every sufficiently large such graph models some combinatorial type of pentagram spiral.
\end{example}

\begin{example}
A $Y$-mesh is a map $(i,j) \to P_{i,j}$ from $\mathbb{Z}^2$ to a projective space such that each translate of a fixed $4$ element subset of $\mathbb{Z}^2$ maps to a quadruple of collinear points.  The second and third authors \cite{GP16} defined  a family of dynamical systems that iteratively build $Y$-meshes of various types.  Each system can be described in terms of mutations of a quiver on a torus \cite[Section 12]{GP16}.  We strongly suspect that vector-relation dynamics on the dual bipartite graph recover the original system.  The only challenge is determining the correspondence between points of the $Y$-mesh and white vertices of the graph.   We focus here on a single illustrative example.

The \emph{rabbit map} acts on the space of triples $A,B,C$ of polygons in $\mathbb{P}^4$ satisfying the conditions
\begin{align*}
& A_{i-1}, B_{i+1}, C_i \textrm{ collinear} \\
& A_{i+1}, B_{i}, C_i \textrm{ collinear} \\
& A_{i-1}, B_{i-1}, B_{i+1}, C_{i+1} \textrm{ coplanar}
\end{align*}
for all $i \in \mathbb{Z}$.  The map takes $(A,B,C)$ to $(B,C,D)$ where
\begin{displaymath}
D_i = \langle A_{i-1}, B_{i+1} \rangle \cap \langle B_{i-1}, C_{i+1} \rangle
\end{displaymath}
for all $i$.  Each quadruple $A_{i-1}, B_{i+1}, C_i, D_i$ of points is collinear, indicating the type of the $Y$-mesh that this system constructs.  

The vector-relation formulation of the rabbit map is given in \cref{fig:rabbit}.  The black vertices correspond exactly to the conditions listed above.  Propagation is carried out by applying urban renewal for each $i$ at the square face containing both $A_{i-1}$ and $B_{i+1}$.

\begin{figure}
\centering
\includegraphics[height=2in]{rabbit.eps}
\caption{The bipartite graph corresponding to the rabbit map.  The figure continues infinitely up and down, while the left and right sides are identified as per the labeling.}
\label{fig:rabbit}
\end{figure}

In general, the bipartite graph perspective represents a significant improvement in our understanding of $Y$-meshes.  As an example, in the original formulation only the cross ratio $y$-variables are easy to describe and the others require a messy case by case analysis \cite[Section 13]{GP16}.  Now we get a uniform description of all $y$-variables via \cref{prop:faceweights}.  For instance, the hexagon in \cref{fig:rabbit} containing $A_3,C_2,B_3$ has weight
\begin{displaymath}
y_F = [A_3, B_2, C_2, A_1, B_3, \langle A_3, B_3 \rangle \cap \langle B_5, C_5 \rangle]^{-1}.
\end{displaymath}
A central question that is open in general is what minimum collections of points determine the $Y$-mesh and what relations they satisfy (see \cite[Section 8]{GP16} for many examples including the rabbit case).  There is hope that these questions have answers in terms of graph theoretic properties of $G$.  A result of this flavor in a different context is given in \cref{prop:matroid}.
\end{example}

\subsection{$Q$-nets} \label{sec:Qnet}
%\section{$Q$-nets and gentrification}

Discrete conjugate nets, or {\it {$Q$-nets}} were introduced by Doliwa-Santini \cite{DS}; we follow the exposition of Bobenko-Suris \cite{BS}.
We shall specifically be concerned with $3$-dimensional $Q$-nets, defined as follows. 

\begin{definition} \cite[Definition 2.1]{BS}
 A map $f: \mathbb Z^3 \rightarrow \mathbb R^3$ is a $3$-dimensional $Q$-net in $\mathbb R^3$ if for every $u \in \mathbb Z^3$ and for every pair of indices $i,j \in \{1,2,3\}$ points $f(u), f(u+e_i), f(u+e_j), f(u+e_i+e_j)$ are coplanar (where $e_1, e_2, e_3$ are the generators of $\mathbb Z^3$).
\end{definition}

While a $Q$-net is a static object, it is often convenient to think of it in a dynamical way as follows. For $u = (i,j,k)$ let $|u| = i+j+k$. A {\it {generation}} of vertices of a $Q$-net is the set of all $f(u)$ where $|u|=t$. Let us denote $f_t$ such $t$-th generation. Then knowing $f_t$ and $f_{t+1}$ one can construct the next generation $f_{t+2}$ as follows. Consider an elementary cube consisting of eight points $f(u+\epsilon_1 e_1+\epsilon_2 e_2 +\epsilon_3 e_3)$, where each $\epsilon_i$ is either $0$ or $1$. Assume $|u|=t-1$. Then using the six points that belong to $f_t, f_{t+1}$ one can construct three planes that have to contain $f(u+e_1+e_2+e_3) \in f_{t+2}$. Intersecting those planes we generically get the unique candidate for $f(u+e_1+e_2+e_3)$. 

The problem of analytic description, which also can be called parametrization of $Q$-nets is discussed in \cite{BS}, with first such description going back to the original work \cite{DS}. Our constructions suggests a new way to parametrize $3$-dimensional $Q$-nets. Furthermore, since our parameters are cross-ratios of quadruples of points, it is natural to view it as parametrizing {\it {projective $Q$-nets}}, i.e. $Q$-nets considered up to projective equivalence. 

Consider three consecutive generations $f_t, f_{t+1}, f_{t+2}$ of a $Q$-net $f$. Their vertices and the edges that connect them can be conveniently visualized as a lozenge tiling dual to the Kagome lattice, see \cref{fig:k1}. Vertices of each lozenge map into vertices of a face of one of the elementary cubes of a $Q$-net, and thus are coplanar. 
Thus, the geometry of the three generations of points is captured by the bipartite graph we get by placing a white vertex at each vertex of the lozenge tiling, and a black vertex at each face, see \cref{fig:k1}.  The set of points of this configuration is sufficient initial data to determine the whole $Q$-net.  In fact, the rest of the $Q$-net is obtained via local transformations, which by an inductive argument boils down to the following.
%Thus, the geometry of the $Q$-net is captured by the bipartite graph we get by placing a white vertex at each vertex of the lozenge tiling, and a black vertex at each face, see \cref{fig:k1}. 

\begin{figure}[h!]
    \begin{center}
    \input{kagome3.pstex_t}
    \end{center}
    \caption{Three generations of a $Q$-net and the associated bipartite graph}
    \label{fig:k1}
\end{figure}

\begin{proposition}
 The sequence of square moves shown in \cref{fig:k2} realizes geometrically a step of time evolution of the $Q$-net transitioning from vertex $D$ to vertex $D'$ of one of the elementary cubes.
\end{proposition}


\begin{figure}[h!]
    \begin{center}
    \input{kagome4.pstex_t}
    \end{center}
    \caption{The gentrification sequence of moves.  For convenience, each black vertex is labeled by the affine hull of the points at neighboring white vertices.}
    \label{fig:k2}
\end{figure}



\begin{proof}
 We verify the sequence of square moves using \cref{prop:evolution} on each step. For example, points $G$ and $H$ are formed by intersecting line $CD$ with affine spans of the rest of black points surrounding respectively $a'$ and $b'$, i.e. with lines $BA'$ and $AB'$. Here $E = C'D' \cap AB'$, $F = C'D' \cap BA'$, $G=A'B \cap CD$, $H=AB' \cap CD$, $a = \langle AB'D'C' \rangle$, $b = \langle A'BC'D' \rangle$, $c = \langle B'CA'D' \rangle$, $e = AB'$, $f = C'D'$, $g = A'B$, $h = CD$, $a' = \langle A'BDC \rangle$, $b' = \langle AB'CD \rangle$, $c' = \langle ADBC' \rangle$.
\end{proof}

\begin{remark}
 This sequence of square moves has appeared in \cite[Figure 8]{KLRR}, without the current geometric interpretation, and under the name of {\it {star-triangle move}}. Here we introduce the name {\it {gentrification}} to emphasize its similar, but not coinciding nature with {\it {superurban renewal}} of \cite{KP}, see below. 
\end{remark}

%\subsection{Analytic desription}

Denote $Q_{i,j,k}$ the vertex of the Q-net with coordinates $i,j,k$, and denote $Q_{i,j,k}^x$ the edge pointing from this vertex in the $x$ direction, i.e. the edge connecting $Q_{i,j,k}$ with $Q_{i+1,j,k}$. Same for $Q_{i,j,k}^y$ and $Q_{i,j,k}^z$.  The vertices of the tiling on the left of \cref{fig:k1} are home to three generations of the $Q$-net, say $f_t, f_{t+1}, f_{t+2}$.  As such the edges correspond to the $Q_{i,j,k}^*$ with $i+j+k \in \{t,t+1\}$ and $* \in \{x,y,z\}$.  Meanwhile, the faces of the bipartite graph correspond to the edges of the tiling, with each edge connecting the two white vertices of the corresponding face.  Each face is a quadrilateral with both of its black vertices having degree four.  It follows from \cref{prop:faceweights} that the face variable equals a negated cross ratio with two points being the endpoints of the edge and the others being intersections of the edge with nearby parallel edges of the tiling.  The exact formula depends on whether the edge connects $f_t$ with $f_{t+1}$ or $f_{t+1}$ with $f_{t+2}$.  To this end, define
\begin{align*}
Y_{i,j,k}^x &= -[Q_{i,j,k}, Q_{i,j,k}^x \cap Q_{i,j+1,k}^x, Q_{i+1,j,k}, Q_{i,j,k}^x \cap Q_{i,j,k+1}^x]^{-1} \\
\tilde{Y}_{i,j,k}^x &= -[Q_{i,j,k}, Q_{i,j,k}^x \cap Q_{i,j,k-1}^x, Q_{i+1,j,k}, Q_{i,j,k}^x \cap Q_{i,j-1,k}^x]^{-1}
\end{align*}
The formulas for the variables at $y$ and $z$ edges are obtained from these by performing a cyclic shift of subscripts and a substitution $x \to y \to z \to x$ of superscripts.  

\begin{proposition}
The collection of face weights, also known as the $Y$-seed, corresponding to the above setup is
\begin{displaymath}
\{Y_{i,j,k}^* : i+j+k = t\} \cup \{\tilde{Y}_{i,j,k}^* : i+j+k = t+1\}.
\end{displaymath}
\end{proposition}

 
 \begin{proposition}
  The variables $Y$ evolve according to the following formulas (and their cyclic shifts):
\begin{align*}
\tilde{Y}_{i,j+1,k+1}^x &= (Y_{i,j,k}^y)^{-1} \frac{1 + Y_{i,j,k}^x + Y_{i,j,k}^y Y_{i,j,k}^x}{1 + Y_{i,j,k}^z + Y_{i,j,k}^z Y_{i,j,k}^x} \\
Y_{i+1,j,k}^x &= \tilde{Y}_{i+1,j,k}^xY_{i+1,j-1,k}^xY_{i+1,j-1,k}^y\frac{1 + Y_{i+1,j,k-1}^z + Y_{i+1,j,k-1}^zY_{i+1,j,k-1}^x}{1+Y_{i+1,j-1,k}^x + Y_{i+1,j-1,k}^xY_{i+1,j-1,k}^y}
\end{align*}
for all $i+j+k=t$.
 \end{proposition}


\begin{figure}[h!]
    \begin{center}
    \input{kagome5a.pstex_t}
    \end{center}
    \caption{$Q$-net quiver.}
    \label{fig:k3}
\end{figure}


\begin{proof}
 One simply follows $Y$-variable dynamics of the associated cluster algebra, whose quiver is shown in \cref{fig:k3}. 
\end{proof}

\begin{remark}
 There is of course also $X$-variable cluster dynamics associated with gentrification. Its given by 
$$X_{i,j+1,k+1}^x = \frac{X_{i,j,k}^x X_{i,j+1,k}^z X_{i,j,k+1}^y + X_{i,j,k}^y X_{i,j+1,k}^z X_{i,j,k+1}^x + X_{i,j,k}^z X_{i,j+1,k}^x X_{i,j,k+1}^y}{X_{i,j,k}^y X_{i,j,k}^z}.$$
It is not clear if the $X$-variables have any geometric meaning in terms of $Q$-nets however. 
\end{remark}

\begin{remark}
Several cluster algebra descriptions of geometric systems, including $Q$-nets and discrete Darboux maps, were found independently in collaboration with Fu \cite{AFGR}.  A common situation that in particular holds for $Q$-nets is that there are two distinct sets of geometric quantities that each evolve according to the (coefficient type) dynamics of the same quiver.  One of the goals of \cite{AFGR} is to better understand this phenomenon.
\end{remark}

\subsection{Discrete Darboux maps}
Discrete Darboux maps were introduced by Schief \cite{Sch}; we follow the exposition of Bobenko-Suris \cite[Exercise 2.8, 2.9]{BS}.
We identify the set of edges of a $3$-dimensional cubic lattice with $\mathbb Z^3 \times \{x,y,z\}$ in that each edge is in bijection with a node of $\mathbb Z^3$ and one of the three positive directions $x,y,z$ in which the edge points from that node.  

\begin{definition} \cite[Definition 2.1]{BS} \label{def:Darboux}
 A map $f: \mathbb Z^3 \times \{x,y,z\} \rightarrow \mathbb R^3$ is a $3$-dimensional discrete Darboux map if for every face of the cubic lattice the images of its edges are collinear. In other words,
$$f_{i,j,k}^x, f_{i,j,k}^y, f_{i,j+1,k}^x, f_{i+1,j,k}^y \text{ are collinear, }$$
$$f_{i,j,k}^x, f_{i,j,k}^z, f_{i,j,k+1}^x, f_{i+1,j,k}^z \text{ are collinear, }$$
$$f_{i,j,k}^y, f_{i,j,k}^z, f_{i,j+1,k}^z, f_{i,j,k+1}^y \text{ are collinear. }$$
\end{definition}

\begin{remark}
 In Schief's definition \cite{Sch} the function takes values on faces of a cubic lattice, not edges. However, as Schief himself observes in loc. cit. the two are equivalent since one can consider a dual cubic lattice with vertices corresponding to elementary cubes of the original one. 
\end{remark}

One can think of discrete Darboux maps in a dynamical way in a similar fashion to $Q$-nets. Define the generation of an edge in $\mathbb Z^3 \times \{x,y,z\}$ as the sum of its three coordinates. Then it is easy to see, as pointed out in \cite[Exercice 2.8]{BS}, that each generation determines the next one uniquely. For example, $f_{i+1,j+1,k}^z$ is the intersection of the line connecting $f_{i+1,j,k}^y$ to $f_{i+1,j,k}^z$ with the line connecting $f_{i,j+1,k}^x$ to $f_{i,j+1,k}^z$. The fact that six points $f_{i+1,j,k}^y$, $f_{i+1,j,k}^z$, $f_{i,j+1,k}^x$, $f_{i,j+1,k}^z$, $f_{i,j,k+1}^x$, and $f_{i,j,k+1}^y$ lie in one plane is a necessarily condition that is easily seen to self-propagate. 

The geometry of a discrete Darboux map is captured by the bipartite graph in \cref{fig:k4}. Here on each edge of the lozenge tiling we place a white vertex signifying a point. To force the four points on the sides of a single lozenge to lie on one line we introduce two black vertices inside. It is clear that if the two triples of points lie on one line, then so do all four points. \cref{fig:k4} should be compared for example with \cite[Figure 7]{KP}.

\begin{figure}[h!]
    \begin{center}
    \input{kagome6.pstex_t}
    \end{center}
    \caption{The bipartite graph of a discrete Darboux map}
    \label{fig:k4}
\end{figure}

\begin{proposition}
 The sequence of square moves shown in \cref{fig:k5} realizes geometrically a step of time evolution of the discrete Darboux map transitioning from vertexes $G, H, K$ to vertices $L, M, N$ of the elementary hexahedron. 
\end{proposition}


\begin{figure}[h!]
    \begin{center}
    \input{kagome7.pstex_t}
    \end{center}
    \caption{Superurban renewal.}
    \label{fig:k5}
\end{figure}

\begin{proof}
 We verify the sequence of square moves using \cref{prop:evolution} on each step. 
\end{proof}

\begin{remark}
 This sequence of square moves has appeared in \cite[Figure 6]{KP}, without the current geometric interpretation, under the name of {\it {superurban renewal}}. 
\end{remark}


%\subsection{Analytic desription}

\cref{prop:faceweights} suggests we introduce the following variables, one for each region in \cref{fig:k4}. For the variables associated with lozenges we get 
$$Y_{ijk}^{xy} = -[f_{ijk}^x, f_{i+1,j,k}^y, f_{i,j+1,k}^x, f_{ijk}^y]^{-1},$$ and similar formulas for other pairs of indexes. 
The variables associated with vertices of lozenges come in three flavors, as there are three generations of them present in the picture. 
\begin{align*}
Y_{ijk}^{\textrm{in}} &= [f_{ijk}^x, f_{i+1,j,k}^y, f_{ijk}^y, f_{i,j+1,k}^z, f_{ijk}^z, f_{i,j,k+1}^x]^{-1}, \textrm{ for $i+j+k=t$} \\
Y_{ijk}^{\textrm{mid}} &= -[f_{ijk}^x, f_{i,j,k-1}^x, f_{i,j,k-1}^z, f_{i,j+1,k-1}^z, f_{ijk}^y, f_{i-1,j,k}^y, f_{i-1,j,k}^x, f_{i-1,j,k+1}^x, \\
& \quad \quad \quad f_{ijk}^z, f_{i,j-1,k}^z, f_{i,j-1,k}^y, f_{i+1,j-1,k}^y]^{-1}, \textrm{ for $i+j+k=t+1$} \\
Y_{ijk}^{\textrm{out}} &= [f_{i-1,j,k}^x, f_{i-1,j-1,k}^y, f_{i,j-1,k}^y, f_{i,j-1,k-1}^z, f_{i,j,k-1}^z, f_{i-1,j,k-1}^x]^{-1}, \textrm{ for $i+j+k=t+2$}.
\end{align*}
The quiver is shown in \cref{fig:k6}. The $Y$-s evolve according to the $Y$-dynamics formulas of the associated cluster algebra. The formulas are too long to be written here. 


\begin{figure}[h!]
    \begin{center}
    \input{kagome8.pstex_t}
    \end{center}
    \caption{Discrete Darboux map quiver.}
    \label{fig:k6}
\end{figure}
 
\begin{remark}
 The  $X$-variable dynamics associated with this quiver and sequence of mutations has appeared in \cite[Lemma 2.3]{KP}, see the formulas given there.
\end{remark}

\begin{remark}
The notions of $Q$-nets and discrete Darboux maps are related by projective duality.  As such, it is interesting that we get distinct quivers for these two systems.  It is unclear if there is a good notion of projective duality on the level of vector-relation configurations in general.
\end{remark}

\end{comment}

\section{Configurations on plabic graphs} \label{sec:plabic}
\subsection{Background on positroid varieties} \label{sec:background}
We now return to the plabic graph case.  The proof of \cref{thm:plabic} utilizes a significant amount of the theory of positroid varieties.  We begin by reviewing the relevant material, generally following \cite{MulSpe} and \cite{LamCDM}.

Given a $k \times n$ matrix $A$, and $J \subseteq \{1,\ldots, n\}$ of size $k$, let $\Delta_J(A)$ denote the maximal minor of $A$ using column set $J$.  The totally nonnegative Grassmannian is the set of $A \in Gr(k,n)$ for which $\Delta_J(A)$ is real and nonnegative for all $J$.  The \emph{matroid} of any $A \in Gr(k,n)$ is 
\begin{displaymath}
\mathcal{M} = \{J : \Delta_J(A) \neq 0\}.
\end{displaymath}  
A \emph{positroid} is a set of $k$-element subsets of $\{1,\ldots, n\}$ that arises as the matroid of a point in the totally nonnegative Grassmannian.  We also denote a positroid by $\mathcal{M}$ even though this is a more restrictive notion than a matroid.

Let $\mathcal{M}$ be a positroid.  For $j=1,\ldots,n$, consider the column order $j < j+1 < \ldots < n < 1 < \ldots < j-1$.  Let $I_j$ be the lexicographically minimal element of $\mathcal{M}$ relative to this order.  The collection of sets $(I_1,\ldots, I_n)$ is called the \emph{Grassmann necklace} of $\mathcal{M}$.  The positroids index a decomposition of the complex Grassmannian by \emph{open positroid varieties} $\Pi_{\mathcal{M}}^{\circ}$, defined as intersections of cyclic shifts of Schubert cells encoded by $(I_1,\ldots, I_n)$.  The \emph{positroid variety} $\Pi_{\mathcal{M}}$ is defined to be the Zariski closure of $\Pi_{\mathcal{M}}^{\circ}$.  In order to give quicker definitions, we fall back on the literature.

\begin{theorem}[Knutson--Lam--Speyer \cite{KLS}]
The positroid variety $\Pi_{\mathcal{M}}$ is a closed irreducible variety defined in the Grassmannian by
\begin{displaymath}
\Pi_{\mathcal{M}} = \{A \in Gr_{k,n} : \Delta_J(A) = 0 \textrm{ for all } J \notin \mathcal{M}\}. 
\end{displaymath}
\end{theorem}

Let $G=(B \cup W, E)$ be a plabic graph.  Following our conventions, all boundary vertices are white.  Let $n$ be the number of boundary vertices and $k = |W| - |B|$.  An almost perfect matching is a matching in $G$ that uses all internal vertices.  Hence it is a matching of $B$ with $W \setminus J$ where $J \subseteq \{1,\ldots, n\}$ (identified with the boundary vertices) and $|J| = k$.  The \emph{positroid} of $G$, denoted $\mathcal{M}_G$ is the set of $J$ that arise this way as the unused vertices of an almost perfect matching.

An \emph{arc} in a plabic graph is a direct path connecting the midpoints of two edges which meet at a vertex and are also part of a common face.  The arc looks something like a circular arc centered at the common vertex, and it is oriented clockwise (resp. counterclockwise) if the vertex is white (resp. black).  Near a boundary vertex an arc is also allowed to begin or end at a nearby boundary point.  A \emph{strand} is a maximal oriented path that decomposes into arcs.  The collection of strands together is called the \emph{alternating strand diagram} of the graph.  One example of such a diagram is given in \cref{fig:strand}.

\begin{figure}
\centering
\includegraphics[height=2.5in]{strand.eps}
\caption{The alternating strand diagram for a plabic graph (left) and the associated labeling by sets of the faces and vertices of the graph (right)}
\label{fig:strand}
\end{figure}


Say a plabic graph $G$ is reduced if its alternating strand diagram has the following properties:
\begin{itemize}
\item All strands start and end at the boundary.
\item No strand has a self intersection unless it corresponds to a degree $1$ boundary vertex whose neighbor is also degree $1$.
\item No pair of strands have a pair of intersections that they encounter in the same order.
\end{itemize}

If $G$ is reduced then there are exactly $n$ strands, one starting near each boundary vertex.  Call $j$ the number of the strand starting near vertex $j$.  The strands divide the disk into regions.  For each $j$, add a label of $j$ to each region lying to the left of strand number $j$ as it is traversed.  Each region corresponds naturally to a white vertex, black vertex, or face of $G$.  Use the notations $S_w$, $S_b$, and $S_F$ to denote the set of labels received by the region in the strand diagram associated to $w$, $b$, or $F$ (see the right of \cref{fig:strand} for an example).

\begin{proposition} \label{prop:labels}
Let $F$ be a face of $G$, $b \in B$, and $w \in W$.
\begin{itemize}
\item $|S_F| = k$, $|S_w| = k-1$, and $|S_b| = k+1$.
\item If $b$ and $w$ are on the boundary of $F$ then $S_w \subseteq S_F \subseteq S_b$.
%\item $S_F \in \mathcal{M}$.
\end{itemize}
\end{proposition}



\subsection{Recasting the main result}
The remainder of this section is devoted to outlining the proof of \cref{thm:plabic}, and we begin by reformulating this result.  Let $G= (B \cup W, E)$ be a plabic graph with all the notation of \cref{subsec:plabic}.  Recall in this setting we only allow gauge transformations at the internal vertices.  Let $\mathcal{C}^{\circ}_G$ denote the space of gauge equivalence classes of vector-relation configurations on $G$ satisfying the circuit condition modulo the action of $GL_k(\mathbb{C})$.

If $(\v, \Rvec) \in \mathcal{C}_G$ then by assumption $v_1,\ldots, v_n$ span $V = \mathbb{C}^k$.  The $v_i$ are defined up to a common change of basis so $A = [v_1 \cdots v_n]$ is a well-defined point of $Gr_{k,n}$.  We use $\Phi$ to denote the map $\Phi:\mathcal{C}^{\circ}_G \to Gr_{k,n}$ taking $(\v, \Rvec)$ to $A$, and we call $\Phi$ the \emph{boundary restriction map}.  In this language \cref{thm:plabic} can be stated as follows.

\begin{theorem} \label{thm:main}
Let $G$ be a reduced plabic graph.
\begin{enumerate}
\item The map $\Phi$ is injective.
\item The Zariski closure of the image of $\Phi$ is the positroid variety $\Pi_{\mathcal{M}}$.
\end{enumerate}
\end{theorem}

\subsection{The reconstruction map} 
In this subsection, we discuss the proof of \cref{thm:main}.  Specifically, we define a rational map $\Psi: \Pi_{\mathcal{M}} \to \mathcal{C}_G^{\circ}$ which turns out to be the inverse of $\Phi$.  As $\Psi$ has the effect of reconstructing the entire configuration from just the boundary vectors, we term it the \emph{reconstruction map}.  


Fix $A \in \Pi_{\mathcal{M}}$ and in fact fix a particular matrix representative so that the columns $v_1,\ldots, v_n$ of $A$ all live in $V$.  Let $H_j \subseteq V$ denote the linear span of $\{v_i : i \in I_j \setminus \{j\}\}$.  For each $w \in W$, define
\begin{equation} \label{eq:reconstruct}
L_w = \bigcap_{j \in S_w} H_j.
\end{equation}

\begin{lemma} For generic $A \in \Pi_{\mathcal{M}}$:
\begin{enumerate}
\item Each $H_j$ is a hyperplane.% with orthogonal complement spanned by $v_j'$.
\item The set $\{H_j: j \in S_F\}$ of $k$ hyperplanes are in general position for each face $F$.
\item Each $L_w$ is a line.
\end{enumerate}
\end{lemma}

\begin{proposition} \label{prop:circuit}
Let $b \in B$ and choose nonzero vectors $v_w \in L_w$ for each neighbor $w$ of $b$.  Then these $v_w$ satisfy a unique linear relation up to scale, and this relation has all coefficients nonzero.
\end{proposition}

\begin{proposition} \label{prop:existence}
Let $A \in \Pi_G$ be generic.  Then there exists a unique configuration $(\v,\Rvec) \in \mathcal{C}_G^{\circ}$ such that $\Phi(\v,\Rvec) = A$ and $v_w \in L_w$ for all $w \in W$.  
\end{proposition}

We now have our definition of the reconstruction map $\Psi: T_G \to \mathcal{C}_G^{\circ}$, namely it maps $A$ to the configuration given by \cref{prop:existence}.  Clearly $\Phi \circ \Psi$ is the identity.  In plainer terms we have existence of an extension of generic $A \in \Pi_{\mathcal{M}}$ to a full configuration.  The following result establishes uniqueness.

\begin{proposition} \label{prop:uniqueness}
Let $(\v,\Rvec) \in \mathcal{C}_G^{\circ}$ and suppose $A = \Phi(\v) $.  Then $(\v,\Rvec) = \Psi(A)$.
\end{proposition}


\begin{example}
Consider the plabic graph $G$ in \cref{fig:strand}.  As previously discussed, $G$ corresponds to the uniform matroid in $Gr_{3,6}$, and it follows that $I_j = \{j,j+1,j+2\}$ with indices modulo $6$.  Given $A = [v_1 \cdots v_6]$ then, $H_i = \langle v_{i+1}, v_{i+2} \rangle$.  The unique internal white vertex $w$ has $S_w = \{3,6\}$, so 
\begin{displaymath}
L_w = H_3 \cap H_6 = \langle v_4,v_5 \rangle \cap \langle v_1, v_2 \rangle.  
\end{displaymath}
One obtains a full configuration $\Psi(A)$ by picking $v_w \in L_w$.  On the other hand, \cref{ex:gr36} explains that any extension must have $v_w$ on this line verifying \cref{prop:uniqueness} in this case.
\end{example}


\acknowledgements{We thank Lie Fu, Rick Kenyon, and Kelli Talaska for many helpful conversations.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
%\printbibliography


\printbibliography

\end{document}
