Ben Braun’s Mathematics Weblog

Thickness of graphs

August 13, 2008 · No Comments

Here is an interesting problem I heard about during a talk by Ellen Gethner. Given a graph $G$ , the thickness of $G$ is the least size of a collection of planar graphs on the vertices of $G$ such that $G$ is the union of these planar graphs. This is related to things like layering electrical circuits on a chip with multiple layers. The thickness is an interesting invariant. In particular, the following question exists: What is the maximal chromatic number of a graph of thickness $t$ ? For each $t\geq 3$ , this value is known to be one of $6t,6t-1,6t-2$ , though which of these is the correct answer for each $t$ is still unknown. For $t=2$ , this value is one of $9,10,11,12$ . For $t=1$ , this is the celebrated four-color theorem for planar graphs. A recent paper by Gethner and others in the Journal of Graph Theory (a preprint is available on Gethner’s website) provides an infinite family of chromatic number $9$ graphs with thickness $2$ . I think this is a beautiful problem and worthy of more attention.

→ No CommentsCategories: Combinatorics

Reflections on Mathfest 2008

August 3, 2008 · No Comments

Mathfest 2008, held in beautiful Madison, WI, has just finished up. As I am sitting in a coffeehouse on State Street, I would like to share some of the mathematical highlights.

Erik Demaine, Hedrick Lecturer. Erik Demaine gave a phenomenal triple of talks about Folding, Algorithms, Art, Magic, Transformers, Reconfigurable Robots, and other equally cool stuff. A highlight for me was the discussion on Saturday of the recent proof that given any finite set of polygons, all having equal area, in the plane, there exists a hinged dissection of one of them that allows a hinged transformation to any of the others! Amazing. Another highlight was his discussion of modern technical origami; I have not paid too much attention to origami since I was in elementary school, but examples like this blew my mind completely. A wonderful synthesis of algorithms and art.
The minicourse I took on the Geometry of Voting from Don Saari of UC - Irvine. I highly recommend for non-mathematicians and mathematicians alike his book Chaotic Elections. Hopefully in the future I will be able to post some more thoughts about the mathematics behind elections and voting.

→ No CommentsCategories: Conferences

Pebbles on the Beach

July 21, 2008 · No Comments

The banner photo for this website is from a beach on the island of Sandon in the Stockholm Archipelago. In May and June 2008, we took a family trip to Stockholm in conjunction with my attendance at the Festive Combinatorics conference in honor of Anders Bjorner. This was a beautiful conference, certainly one of the best I have attended. Making it all the more enjoyable was that my wife completed the Stockholm Marathon the day after the conference ended! Excellent.

→ No CommentsCategories: Uncategorized

Cohen Macaulay Algebras and Non-negativity

July 18, 2008 · 1 Comment

One element of topological and algebraic combinatorics that I found very difficult to understand as a graduate student was the Cohen-Macaulay property for a graded algebra. In particular, the Hilbert series of a standard graded Cohen-Macaulay algebra has non-negative integer coefficients in the numerator polynomial when represented as a rational function. This non-negativity result is extremely powerful; for some consequences, see the book Combinatorial Commutative Algebra, by Miller and Sturmfels, section 13.4, or the book Combinatorics and Commutative Algebra by Richard Stanely. This post is an attempt to make clear, on a very basic level, why the non-negativity result is true.

In the following, assume for simplicity that all our algebras are $\mathbb{N}$ -graded $\mathbb{C}$ -algebras. Let’s begin with an example.

Consider the standard two-dimensional simplex, i.e. the polytope $\Delta_2=\textrm{conv}\{(0,0),(1,0),(0,1)\}$ . The cone over $\Delta_2$ , denoted $\mathcal{C}[\Delta_2]$ , is defined as the set of all non-negative real linear combinations of the vectors $\{(0,0,1),(1,0,1),(0,1,1)\}$ . Consider the semigroup algebra $\mathbb{C}[\Delta_2]$ given by the set of all integer points in the cone over $\Delta_2$ . It is not hard to see that

$\mathbb{C}[\Delta_2] = \left\{ \sum \mathbf{a}_{a_1,a_2,t}x_1^{a_1}x_2^{a_2}x_3^t: a_1+a_2\leq t, \mathbf{a}_{a_1,a_2,t}\in \mathbb{C}, \left| \{ \mathbf{a}_{a_1,a_2,t} \neq 0 \} \right| < \infty \right\}.$

For a non-negative integer $t$ , the number of lattice points in $t\Delta_2$ is equal to the number of non-negative integer solutions to the equation $a_1+a_2\leq t$ . This is also the number of monomials in the $t^{th}$ graded component of $\mathbb{C}[\Delta_2]$ , where the grading is by the $t$ -value. Finally, if we change variables in our example and write $\theta_1=x_1x_3,\theta_2=x_2x_3,$ and $\theta_3=x_3$ , then $\mathbb{C} [\Delta_2] \cong \mathbb{C} [\theta_1,\theta_2,\theta_3]$ , where $\mathbb{C}[\theta_1,\theta_2,\theta_3]$ is endowed with the standard grading.

The realization of $\mathbb{C}[\Delta_2]$ as a polynomial ring in three variables is an instance of the Cohen-Macaulay condition.
Let’s see how this works in general. Given a graded algebra $A$ , an element $a\in A$ is called homogeneous of degree $i$ if $a\in A_i$ for some $i$ .
We say that homogeneous elements $a_1,\ldots, a_k\in A$ are algebraically independent if for all $f\in \mathbb{C}[x_1,\ldots,x_k]$ such that $f(a_1,\ldots,a_k)=0$ , we have $f(x_1,\ldots,x_k)=0$ as a polynomial.

The first tool we need to introduce is the Noether Normalization Lemma, which states that our finitely generated algebra $A$ contains a polynomial ring $\mathbb{C}[\theta_1,\ldots,\theta_d]$ such that $A$ is a finitely generated $\mathbb{C}[\theta_1,\ldots,\theta_d]$ -module.

Noether Normalization Lemma Let $A=\oplus_{t\in \mathbb{Z}_{\geq 0}}A_t$ be a finitely generated algebra. Then there exist a finite number of homogeneous elements $\theta_1,\ldots,\theta_d$ such that

the elements $\theta_1,\ldots,\theta_d$ are algebraically independent over $\mathbb{C}$ ; and
there exist a finite number of homogeneous elements $\eta_1,\ldots,\eta_s$ such that each element $a\in A$ can be expressed in the form
$a=\sum_{i=1}^s\eta_i p_i(\theta_1,\ldots,\theta_d),$

where each $p_i(\theta_1,\ldots,\theta_d)$ is a polynomial in $\theta_1,\ldots,\theta_d$ which depends on $a$ .

The sequence $\theta_1,\ldots,\theta_d$ is called a system of parameters for $A$ . It can be shown that the number $d$ , called the Krull dimension of $A$ , is uniquely determined by $A$ . It is also not hard to see that the Krull dimension of $A$ is 0 if and only if $A_t=0$ for all sufficiently large $t$ . A system of parameters is called regular if, for some choice of $\eta_1,\ldots,\eta_s$ in the second condition of the Noether Theorem, the coefficients $p_i(\theta_1,\ldots,\theta_d)$ are unique for every $a\in A$ . The existence of regular systems of parameters is an important condition, earning the following special designation: A finitely generated algebra $A$ is called Cohen-Macaulay if some system of parameters for $A$ is regular. The Cohen-Macaulay condition implies that $A$ is a free module over the polynomial ring, i.e. a direct sum of polynomial rings (not all necessarily generated by degree $1$ elements).

As another example, consider the following sub-algebra of $\mathbb{C}[x]$ :

$\mathcal{P}_3 := \mathbb{C}[1,x^3,x^{4},x^{5}].$

Following the notation of the Noether Normalization Lemma, if we let $\theta_1=x^3$ , then $\mathcal{P}_3$ is a module over $\mathbb{C}[x^3]$ generated by $\{1,x^{4},x^{5}\}$ . If we set $\eta_1=x^{4},\eta_{2}=x^{5},\eta_3=1$ , then each element of $\mathcal{P}_3$ has a unique representation in the form of the second condition of the Noether Lemma. This can be seen by first noting that the elements of $\mathcal{P}_3$ are linear combinations of a constant term and monomials with exponent greater than or equal to $3$ . By looking at the residue classes of the exponents of such monomials modulo $3$ , we can group terms by residue class and hence get our unique expression. Thus, $\mathcal{P}_3$ is Cohen-Macaulay of Krull dimension one. Specifically,

$\mathcal{P}_3\cong_{\mathbb{C}[x^3]} \mathbb{C}[x^3]\oplus \mathbb{C}[x^3](-4) \oplus \mathbb{C}[x^3](-5),$

where the notation indicates that the grading on the second and third summands is increased by $4$ and $5$ , respectively. Note that this decomposition implies that the Hilbert series of $\mathcal{P}_3$ is $H(\mathcal{P}_3;z)=\frac{1+z^4+z^5}{(1-z^3)}.$

Our two examples above illustrate how a finitely generated Cohen-Macaulay algebra $A$ can be represented as a direct sum of isomorphic polynomial rings, with the number of variables in the polynomial rings determined by the Krull dimension of $A$ . As demonstrated in our second example, the grading of each summand might be shifted. One may also consider polynomial rings where the variables are not all of degree $1$ , for example the polynomial ring $\mathbb{C}[x_1,\ldots,x_d]$ , where the degree of $x_i$ is denoted by $e_i$ . It is easy to see that the Hilbert series for $\mathbb{C}[x_1,\ldots,x_d]$ collapses as the following rational generating function:

$H(\mathbb{C}[x_1,\ldots,x_d];x)= \frac{1}{\prod_{i=1}^d(1-x^{e_i})}.$

Given that a Cohen-Macaulay algebra $A$ is a direct sum of polynomial rings in $d$ variables, one would expect that the Hilbert series for $A$ would be a (possibly shifted) sum of Hilbert series of the form in our last example. This indeed turns out to be the case; the following theorem provides the non-negativity we were looking for. It occurs because we are looking at direct sums where the summands have shifted gradings!

Theorem Suppose that $A=\oplus_{t\in \mathbb{N}_{\geq 0}}A_t$ is Cohen-Macaulay of Krull dimension $d$ . Let $\theta_1,\ldots,\theta_d$ be a system of parameters with $\theta_i$ of degree $e_i>0$ . Then for some $s\geq 0$ , the Hilbert series $H(A;x)$ is of the form $H(A;x)=\frac{h_0+h_1x+h_2x^2+\cdots+h_sx^s}{\prod_{i=1}^d(1-x^{e_i})},$ with each $0\leq h_j\in \mathbb{Z}$ .