Posets of trek polynomials for directed trees

Abstract

When a variety $V_{\phi }$ equals the image of a polynomial map $\phi$ whose coordinate functions are combinatorial generating polynomials (i.e.~polynomials enumerating combinatorial objects), the geometry of $V_{\phi }$ reflects identities satisfied by the generating polynomials. The resulting interplay between combinatorics and algebraic geometry can be used to answer questions about $V_{\phi }$. A recent technique proposes to do so using a partially ordered set (poset) $P_{\phi }$ defined via the coefficient vectors of the polynomials defining $\phi$. This paper characterizes the poset $P_{\phi }$ when the generating polynomials defining $\phi$ enumerate subgraphs of a directed tree known as treks. The characterization is used to compute the linear span of $V_{\phi }$, prove it is toric and deduce a basis for its vanishing ideal. It is also shown that this poset of trek polynomials for a directed tree is a so-called $\pi$-system if and only if the tree satisfies a property characterized via Stanley's P-partitions. As an additional consequence, it is shown that the varieties for two distinct directed trees intersect in a strictly lower-dimensional variety. This solves an instance of the structural identifiability problem in the graphical models program from statistics.