Using Binomial Ideals For Combinatorics

We have seen that combinatorics is useful to understand decompositions of binomial ideals, but one can also use decompositions of binomial ideals to understand combinatorics.

Consider $\mathbb{N}^{n}$, the set of lattice points in the non-negative orthant. Any finite set $\mathcal{B} \subset \mathbb{Z}^{n}$ defines a graph $G_{\mathcal{B}}$ on $\mathbb{N}^{n}$ with edge set given by all translates of $\mathcal{B}$. Binomial algebra can be used to study connectivity of this graph, a common task in algebraic statistics, combinatorial game theory, integer programming, and other areas working with lattice points.

  1. Consider the polynomial ring $\newcommand{\<}{\langle}\renewcommand{\>}{\rangle}\newcommand{\NN}{\mathbb{N}}\newcommand{\kk}{k}\newcommand{\ZZ}{\mathbb{Z}}\kk[x_{1},\dots,x_{n}]$ and the binomial ideal $I_{\mathcal{B}} := \<x^{b^{+}} - x^{b^{-}} : b \in \mathcal{B}\>$ where[[ $b^{\pm}_{i} = \max\{\pm b_{i}, 0\}$]] such that $b = b^{+} - b^{-}$
  2. Convince yourself that $u,v\in \NN^{n}$ are connected by moves from $\mathcal{B}$ (without leaving $\NN^{n}$!) if and only if $x^{u} - x^{v} \in I_{\mathcal{B}}$.
  3. What kind of statements can you make about the connectivity of $G_{\mathcal{B}}$ if $I_{\mathcal{B}} = J_{1}\cap \dots \cap J_{r}$ is a primary decomposition? What about a mesoprimary decomposition?
  4. Describe the graphs on $\NN^{2}$ defined by $\mathcal{B}_{1} = \{(2,-2), (3,-3)\}$ and $\mathcal{B}_{2} = \{(1,1), (2,-1)\}$. Draw the graph on paper to check any algebraic results you get.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License