Combinatorics Seminar: Money changing problems on affine semigroups

Seminar | February 12 | 12-1 p.m. | 939 Evans Hall

Jesus De Loera, UC Davis

Department of Mathematics

An affine semigroup is a semigroup (always containing a neutral element) which is finitely generated and can be embedded in $Z^d$ . I care about them because they are the algebraic combinatorics analogues of convex polyhedral cones and because they are at the cross-roads of convex geometry, algebraic geometry, commutative algebra and combinatorics among others (e.g., they constitute the combinatorial background for the theory of toric varieties and appears in the study of algorithms in integer optimization). An affine semigroup can be seen as $\text {Sg}(A)=\{b: b=Ax, x \in Z^n, x\geq 0 \}$ and $A$ is an integer $d \times n$ matrix. Of course if $d=1$, $A$ is just a list of coin values. Each such vector $x$ is a \emph {membership representation} of $b$ in the semigroup $\text {Sg}(A)$ and, for $d=1$, membership has a monetary meaning as a denomination one can make change for using the given coin values.

My talk considers two questions about the representations of the members of an affine semigroup in terms of its generators (i.e., the columns of $A$).

1) I describe the set of all elements in the semigroup $\text {Sg}(A)$, that have at least k different representations. We will see how this generalizes the Frobenius coin problem.

2) I look at the problem of representing an element of $\text {Sg}(A)$ with the sparsest representation, i.e., using the fewest possible generators. A special case is giving change using the fewest kinds of coins. We provide a bound in terms of $A$ which are asymptotically best possible.

This work is joint work with subsets of the following researchers: Iskander Aliev, Quentin Louveaux, Timm Oertel, Chris O'Neill, Fritz Eisenbrand, and Robert Weismantel. Aiming to make this accessible to students or anyone that likes coin puzzles, all my examples will involve money!

events@math.berkeley.edu