A note on toric ideals of graphs and Knutson-Miller-Yong decompositions

Abstract

We use a Gröbner basis technique first introduced by Knutson, Miller and Yong to study the interplay between properties of a graph $G$ and algebraic properties of the toric ideal that it defines. We first recover a well-known height formula for the toric ideal of a graph $I_G$ and demonstrate an algebraic property that can detect when a graph deletion is bipartite. We also bound the chromatic number $\chi (G)$ using information about an initial ideal of $I_G$.

12 pages, 1 figure