Math Explorers Club
Graphs, Partially Ordered Sets and Polynomials
Tuesday, January 27, 2009
We will approach “graphs and polynomials” in three ways - the first, and easier, will be to show how given a bunch of polynomials (or just natural numbers), we can make a graph that represents their least common multiples. This is a very special type of graph called a “partially ordered set” or “poset” for short. Posets occur in the natural world with an incredible frequency.
In this particular case, we are looking at something called the “least common multiple poset” (or “lcm poset”) of the numbers 2,4,3, and 5. A “poset” is a graph where the vertices are arranged in such a way that we have some ordering on vertices where some vertices are “higher” than others. It would need to satisfy a few properties (namely, that if we had vertices a,b and c, and 
, 
, then 
as well as 
and 
means that 
.) When we draw our poset, we denote this “greater than or equal to” relationship by placing a vertex “above” another vertex in the picture.
For this lcm poset, we say that 
if a divides b. Looking above, we see that this is always the case in the picture!
Exercise: Show that 
if a divides b gives us a poset on the natural numbers.
Exercise: Draw the lcm poset for the numbers 2,4,8 and 5.
The second way we’ll run into polynomials will be to actually represent the edges of our graph as polynomials of degree two, and consider how many different polynomials we can make as sums or multiples of these. Given a graph, there is a special set of polynomials we can associate to it called its “edge ideal,” an object that numerous combinatorialists across the world study to this day.
The third will be to consider a number of different polynomials associated with graphs. Combinatorialists that study graphs will often use these polynomials to give them information about the graphs they are studying - for example, even if calculating whether two graphs are really the same graph (“isomorphic”), sometimes it’s easier to calculate one of these special polynomials associated to each of the graphs and check and see if they are the same. While having the same polynomial may or may not mean that they are isomorphic, having different polynomials would indicate they were different graphs.
Let’s go to our third set of polynomials. The easiest one to calculate is the only one we’ll focus on today - it’s called the “Tutte polynomial.”
