former graduate students
- Eric Etu (Computer Science) -- Computation of characteristic polynomials of hyperplane arrangements (May 07)
A hyperplane arrangement is a finite set of hyperplanes. Much of the combinatorial structure of a hyperplane arrangement is encoded in its characteristic polynomial, which is defined recursively through the intersection lattice of the hyperplanes. For example, the number of regions that are cut out in space by the hyperplane arrangement is a special evaluation of the characteristic polynomial. Eric developed an algorithm and software to compute characteristic polynomials of hyperplane arrangements. - Mary Halloran -- Finite trigonometric character sums via discrete Fourier analysis (May 07)
Certain curiously-looking finite trigonometric sums follow as corollaries of (nontrivial) functional equations of Dedekind, Ramanujan, Rademacher, and others. An illustrative example for such a trigonometric identity is Sumk=1...a-1 tan2(pi k/a) = a(a-1), which holds for any positive integer a. Recently, Berndt-Yeap and Berndt-Zaharescu collected a litany of these finite trigonometric sums and showed how they can be proved using contour integration of Complex Analysis. Mary proved similar identities using methods of discrete Fourier Analysis. We subsequently wrote a joint paper. - Asia Matthews -- A geometric approach to Carlitz-Dedekind sums (May 07)
A Carlitz polynomial is the polynomial generalization of the Dedekind sum, which in turn is an arithmetic sum playing a central role in various mathematical areas, such as theta functions, group actions on manifolds, and integer-point enumeration in polytopes. The most important property of any Dedekind-like sum is reciprocity: adding up Dedekind sums while cyclically varying their parameters gives a simple function in those parameters. Carlitz proved such a reciprocity law for his polynomials. Asia gave a novel geometric proof of this reciprocity law, as well as new reciprocity theorems. She also discovered two new theorems relating Carlitz polynomials to the generating function of two and three-dimensional simplices. We subsequently published a joint paper (with C. Haase) in Mathematische Annalen. - Dorothy Moorefield -- Partition Analysis and Ehrhart Theory (December 06)
In the early 1900s, Percy A. MacMahon developed the Omega operator as a tool for enumerating partitions via their corresponding Diophantine relations. Dorothy discussed various algorithms for applying the Omega operator and showed how MacMahon's methods can be applied to the problem of enumerating lattice points in polyhedra. Corteel, Lee and Savage have developed five guidelines that provide a simplification of MacMahon's partition analysis for integral, linear, homogeneous systems of inequalities. Dorothy expanded on these guidelines to include linear systems of equalities. - Kim Seashore -- Growth series of root lattices (August 07, coadviser: Serkan Hosten)
Let L be a lattice, and let M be a subset that generates L as a monoid. The coordination sequence (SM(n))n>=0 of (L,M) is given by SM(n), the number of elements in L with word length n with respect to M, that is, the number of lattice elements that are expressed as a sum from M with a minimal number of n terms. The growth series GM of L is the generating function of SM(n): GM(x) := sumn>=0 SM(n) xn. Understanding growth series is fundamental to a lot of mathematical problems connected to lattices, for example in coding theory. In a recent paper, Serkan Hosten and I studied the growth series of cyclotomic lattices, based on unimodular triangulations of certain polytopes. Kim extended these methods to lattices coming from the classical root systems of type A and C. - Andrew Van Herick -- Theoretical and Computational Methods for Lattice Point Enumeration in Inside-Out Polytopes (August 07)
The theory of inside-out polytopes was developed to count the number of lattice point within a polytope but outside a set of hyperplanes. Inside-out polytopes have many applications, such as graph colorings and flows, enumeration of magic, latin, and other squares, etc. Andrew introduced two approaches to computing the counting functions associated to inside-out polytopes; one uses mixed integer programming, the other computes the regions of an inside-out polytope and sums the Ehrhart quasipolynomials of the regions. He gave a polynomial-time algorithm for computing the region descriptions in fixed dimension, which yielded a polynomial-time algorithm to compute counting functions for rational inside-out polytopes. He implemented his algorithm in C++ and computed a number of new examples, most notably the counting functions for strict magic 4x4 squares.
current graduate students
- Andrew Beyer -- Enumeration of orthogonal latin squares
A latin square is an nxn matrix, in which the entries in each row and column are distinct. (A classical latin square has the additional restriction that we only use the numbers 1, 2, ..., n as entries.) Two latin squares (aij) and (bij) are orthogonal if the n2 pairs (aij, bij) are distinct. Aside from being interesting combinatorial objects, orthogonal latin squares have important applications in coding theory. Andrew tries to develop a method of enumerating orthogonal latin squares, based on the theory of inside-out polytopes. - Anastasia Chavez -- Bernoulli-Dedekind sums
In the 1880's, Richard Dedekind derived a finite arithmetic sum that today is called the Dedekind sum. Since then the Dedekind sum has appeared in many areas of mathematics such as topology, geometry, and combinatorics. Apostel, Carlitz, and others have introduced Dedekind-like sums involving Bernoulli polynomials. Bernoulli polynomials are defined by a generating function and give rise to the Bernoulli numbers when a polynomial is evaluated at 0, which has also appeared in various mathematical areas. In recent work by Beck, Haase and Matthews, a polynomial analogue of Dedekind sums, the Carlitz polynomial, was used to prove results using discrete geometry. Anastasia plans to use similar geometric methods to reprove known theorems and discover new results of Dedekind sums involving Bernoulli polynomials. - Aaron Dall -- Flow complexes
Recently, Steingrimsson defined the coloring complex of a graph G. He established a one-to-one correspondence between the proper colorings of G and the elements in a certain monomial ideal. This allows one to, e.g., realize the chromatic polynomial of G as the Hilbert polynomial of this ideal. Aaron tries to come up with an analogous construction for flows of G instead of colorings. - Alex Plotitsa -- Computation of counting functions of magic labellings
A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. The most famous class of examples are magic squares (the sets are the rows, columns, and diagonals). It follows from a recent paper of Thomas Zaslavky & myself that the number of nxn magic labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Alex develops software that allows us to compute a large class of example of such counting functions.
