Math

Graph Coloring via Rings

Introduction

While taking a course on ring theory, I looked up some applications of it to other fields. My favorite one was this connection to graph theory, in particular a characterization of the chromatic number from the perspective of ideal theory and algebraic geometry. In fact, there are two completely separate ways of getting to it, and each provides pretty cool insights.

Background

◇ Definition
  1. A commutative ring $R$ is a set with two operations: addition and multiplication. As in the integers, both are associative, commutative, and multiplication distributes over addition. $R$ is closed under the operations, and contains an additive identity $0$ and a multiplicative identity $1$.
  2. A polynomial ring over a field $F$ with one variable, $F[x]$, is the set of polynomials of $x$ with coefficients in $F$. Likewise, $F[x_{1},...,x_{n}]$ is the set of such multivariate polynomials.
  3. An ideal $I\subseteq R$ of a ring is a subset such that:
    1. $\forall a,b\in I,\;a+b\in I$;
    2. $\forall a\in I, r\in R, \;ar\in I$;
  4. An ideal $I$ is generated by $a\in R$, written as $I=\langle a\rangle$, if $I=\set{ar\mid r\in R}$. Likewise, $\langle a_{1},...,a_{n}\rangle=\set{\sum_{i\in[n]}a_{i}r_{i}\mid r_{i}\in R}$. Here, $\set{a_{1},...,a_{n}}$ is the basis of the ideal.
  5. For a set of polynomials $f_{1},...,f_{s}\in F[x_{1},...,x_{n}]$, define the variety $\mathbf{V}(f_{1},...,f_{s})=\set{a=(a_{1},...,a_{n})\in F^{n}\mid f_{1}(a)=...=f_{s}(a)=0}$, that is, the set of common zeroes of the polynomials.
◆ Proposition: Fact 1
In a polynomial ring, if $I=\langle f_{1},...,f_{s}\rangle$ then $\mathbf{V}(f_{1},...,f_{s})=\mathbf{V}(I)$. This means that the variety of an ideal is not determined by the chosen basis.

The first construction

For a graph $G=(V,E)$, consider the multivariate polynomial ring $R=\mathbb{C}[V]$ (with variables being vertices). For an integer $k$, define $I_{k}=\langle v^{k}-1\mid v\in G\rangle\subseteq R$, which is an ideal. We get something interesting when we consider the variety $\mathbf{V}(I_{k})$: if some point $(a_{1},...,a_{n})\in\mathbb{C}^{n}$ is in $\mathbf{V}(I_{k})$, meaning all $v_{i}^{k}-1$ evaluate to $0$ at that point, or $a_{i}^{k}=1$, then each $a_{i}$ is a $k$-root of unity! In other words, the point assigns to each vertex of $G$ a value in $\set{1,\zeta,...,\zeta^{k-1}}$, of which there are $k$, thus we can interpret $\mathbf{V}(I_{k})$ to be the set of all $k$-colorings of $G$. This is cool, but not significant yet, since these colorings are not proper.

Next, we introduce a way to “filter” these colorings. Let

$$f_{G}(v_{1},...,v_{n})=\prod_{(v_{i}v_{j})\in E(G)}(v_{i}-v_{j})\quad \in \mathbb{C}[V].$$

Here, we think of the variables as the assigned colors of vertices. It is easy to see that $f_{G}=0$ if and only if for some two vertices which share an edge, the color assignments are equal. Therefore, this polynomial vanishes exactly on the set of improper colorings.

◆ Theorem: Theorem 1
$G$ is $k$-colorable if and only if $f_{G}\notin I_{k}$.

Proof $(\Rightarrow )$. $f_{G}\in I_{k}$ implies $f_{G}$ vanishes on $\mathbf{V}(I_{k})$; let $a=(a_{1},...,a_{n})$ be a point of the variety, then $0=f_{G}(a)$ implies that for some edge $(v_{i}v_{j})$ we get $a_{i}=a_{j}$. Since $a$ was an arbitrary point corresponding to a $k$-coloring of $G$, all $k$-colorings fail to be proper.

For the reverse direction, we will need to invoke Hilbert’s Nullstellensatz.

◆ Theorem: Hilbert's Nullstellensatz.
If $f\in F[x_{1},...,x_{n}]$ vanishes on $\mathbf{V}(I)$ for some ideal $I$ then $f^{m}\in I$ for some integer $m$.

Proof $(\Leftarrow )$. $G$ being non-$k$-colorable implies any point of $\mathbf{V}(I_{k})$, which corresponds to a $k$-coloring, is not proper, so $f_{G}$ vanishes on it. Applying the Nullstellensatz, we know $f_{G}^{m}\in I_{k}$ for some integer $m$. We see the result follows immediately if $I_{k}$ is a radical ideal.

◇ Definition: Radical ideal
An ideal $I\subset R$ is radical if for any $a$ and integer $m$, $a^{m}\in I\Rightarrow a\in I$.

◆ Proposition
$I_{k}$ is a radical ideal.

To prove this, a bit of machinery is needed. Feel free to skip this if you are content to take the above as fact. First, we use a lemma that gives an alternative characterization of radical ideals; second, I very cautiously introduce tensor product between two rings. I am by no means an expert on this, but for this proof we only need the most basic idea.

◆ Lemma
Ideal $I\subset R$ is radical if and only if quotient ring $R/I$ satisfies $a^{2}=0\Rightarrow a=0$ for all its elements $a$ (this is called a reduced ring).

A tensor product of two polynomial rings $R[x]$ and $R[y]$ over $R$ essentially combines them into a single ring that incorporates both $x$ and $y$: $R[x]\otimes_{R}R[y]\cong R[x,y]$. Moreover, if we have $f(x)\in R[x],\;g(y)\in R[y]$, then $R[x]/\langle f\rangle \otimes_{R}R[y]/\langle g\rangle \cong R[x,y]/\langle f,g\rangle$. This can be thought of by considering the latter’s basis being composed of the product of the bases $\set{1,x,...,x^{\text{deg}(f)-1}}$ and $\set{1,y,...,y^{\text{deg}(g)-1}}$.

Proof of prop. Taking the above as fact, we write:

$$\frac{\mathbb{C}[v_{1},...,v_{n}]}{\langle v_{1}^{k}-1,...,v_{n}^{k}-1\rangle}=\bigotimes_{i\in[n]}\frac{\mathbb{C}[v_{i}]}{\langle v_{i}^{k}-1\rangle},$$

where the tensor product is taken over $\mathbb{C}$. Next we observe that $v^{k}-1=\prod_{j=0}^{k}(v-\zeta^{j})$ by factoring the roots in $\mathbb{C}[v]$. Since this is a PID and for $j\neq j'$ the polynomials $v-\zeta^{j}$ and $v-\zeta^{j'}$ are coprime, $\langle v-\zeta^{j}\rangle$ are all pairwise comaximal, thus the Chinese remainder theorem applies:

$$\mathbb{C}[v]/\langle v^{k}-1\rangle\cong \prod_{j=0}^{k-1}\mathbb{C}[v]/\langle v-\zeta^{j}\rangle\cong \prod_{j=0}^{k-1}\mathbb{C}=\mathbb{C}^{k}$$

where the second isomorphism follows due to $v-\zeta^{j}$ being linear (consider $f(v)\mapsto f(\zeta^{j})$). Now $\mathbb{C}[V]/I_{k}=\mathbb{C}^{k}\otimes_\mathbb{C} ...\otimes_\mathbb{C} \mathbb{C}^{k}=\mathbb{C}^{k^{n}}$; this can be thought of again as multiplying the $k$ bases $n$ times. Finally, take $a=(a_{1},...,a_{k^{n}}) \in\mathbb{C}^{k^{n}}$ and suppose $a^{2}=0=(0,...,0)$. Since each component $a_{i}^{2}=0$ in the field $\mathbb{C}$, it must be that $a_{i}=0\Rightarrow a=0$. Applying the lemma above, we get $I_{k}$ is radical.

Conclusion

This approach constructs the set of all $k$-colorings of $G$ as an affine variety of a carefully chosen ideal, and then filters them based on inclusion of a graph polynomial, thus we get $\chi(G)=\min\set{k\mid f_{G}\not\in I_{k}}$. The computer scientist brain, at this point, is asking: how hard is it to check whether $f_{G}$ is contained in $I_{k}$? To do this, we have to compute the Gröbner basis of the ideal - a particularly nice generating set. This is, unfortunately (but predictably), exponentially hard. This technique does not really give us a more optimal algorithm for graph coloring, but it’s an interesting perspective on a problem that we usually think of as purely combinatorial.

The second construction

# todo :D