**Problem of the Week**

**Math Club**

**BUGCAT 2020**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

seminars:comb:abstract.200612zas

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.

seminars/comb/abstract.200612zas.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported