Finite phylogenetic complexity and combinatorics of tables (Q506179)

In phylogenetics, possible histories of evolution are represented by trees, and to each tree can be associated a certain algebraic variety. Phylogenetic invariants are polynomials that vanish on this algebraic variety and are used to distinguish between phylogenetic trees. In this article, the ideal of phylogenetic invariants is studied for group-based models. These are a family of models for which the associated algebraic varieties are known to be toric [\textit{S. Evans} and \textit{T. P. Speed}, Ann. Stat. 21, No. 1, 355--377 (1993; Zbl 0772.92012); \textit{S. László} et al, Adv. Appl. Math. 14, No. 2, 200--216 (1993; Zbl 0794.05014); \textit{M. Michałek}, J. Algebra 339, No. 1, 339--356 (2011; Zbl 1251.14040)]. For a fixed group \(G\) and the star graph \(K_{1,n}\) with \(n\) leaves, write \(\phi(G,n)\) for the largest degree of a generator for the corresponding ideal of phylogenetic invariants. Then the phylogenetic complexity of \(G\) (see Definition 1.2), denoted \(\phi(G)\), is the maximum of \(\phi(G,n)\) as \(n\) ranges over all positive integers. It is not at all clear that \(\phi(G)\) is finite. The main result of this paper is that the phylogenetic complexity \(\phi(G)\) is finite for any abelian group \(G\). This result presents significant progress towards proving the conjecture of \textit{B. Sturmfels} and \textit{S. Sullivant} [J. Comp. Biol. 12, 204--228 (2005; Zbl 1391.13058)] that \(\phi(G)<|G|\). It is known that binomials in the ideal of phylogenetic invariants correspond to pairs of tables (whose rows are flows) which are compatible in a certain sense. The authors show that compatible tables with a large number of columns can essentially be transformed into one another via quadratic moves (see Definition 2.4, Lemma 3.11). This is the main technical fact which they use to show that \(\phi(G,n)=\phi(G,n+1)\) for \(n\gg 0\), thus proving their result.