Computing linear systems on metric graphs (Q1690779)

A metric graph \(\Gamma\) is a connected undirected graph whose edges have positive lengths. A divisor \(D\) on \(\Gamma\) is a formal finite \(\mathbb Z\)-linear combination \(D=\sum_{x\in \Gamma}D(x).x\) of points \(x\) in the edges of \(\Gamma\). The divisor is effective if \(D(x)\geq 0\) for all \(x\in \Gamma\). A (tropical) rational function \(f\) on \(\Gamma\) is a continuous function \(f : \Gamma\rightarrow\mathbb R\) that is piecewise-linear on each edge of \(\Gamma\) with finitely many pieces and integer slopes. The order \(\mathrm{ord}_x(f)\) of \(f\) at a point \(x\in \Gamma\) is the sum of the outgoing slopes at \(x\) along all directions. The principal divisor associated to \(f\) is \((f)=\sum_{x\in \Gamma}\mathrm{ord}_x(f).x\). For any divisor \(D\) on \(\Gamma\), let \(R(D)\) be the set of all rational functions \(f\) on \(\Gamma\) such that the divisor \(D+(f)\) is effective, and \(| D| =\{D+(f) \mid f \in R(D)\}\) be the linear system of \(D\). In the paper under review, the author focuses on the computation of the cell complex \(| D|\), namely given a metric graph \(\Gamma\) and a divisor \(D\) on it, how to find the cells in \(| D|\) and the \(f\)-vector of \(| D|\). Since \(| D|\) may contain a large number of cells and some of these are complicated, the complexity of computation could be high. In this reason, the author introduces the anchor divisors and anchor cells that serve as the landmarks to compute the \(f\)-vector and all cells of \(| D|\). The author also computes the extremal generators of \(R(D)\) and applies his methods to some examples, namely, the canonical linear systems of some small trivalent graphs.