Thomas Zaslavsky (Binghamton)

Balls into Urns, or, State-Coloring of a Gain Graph

Abstract for the Combinatorics Seminar
2006 December 5

You have an unlimited supply of balls of k different colors, and n labelled urns into which you can put them. Balls of the same color are indistinguishable. You can choose to put any balls into any urns, but you only care which colors are represented in which of the urns. How many ways are there to do this? The answer leads to some interesting generating functions.

It also leads to a generalization of graph coloring. A gain graph is a graph whose edges are orientably labelled from a group. Properly coloring a gain graph means assigning to each vertex an element of a color set which is the disjoint union of copies of the group; i.e., the group has a semiregular action on the color set. The urns problem can be viewed as a coloring problem, if the color set is generalized to allow an arbitrary group action; the generalization of a proper coloring is what is called in physics a totally frustrated state. I will discuss counting such states as a generalization of counting proper colorings.


To the Combinatorics Seminar Web page.