research 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 -- Tension and flow complexes (SFSU Mathematics MA December 08)
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 came up with analogous constructions for tensions and flows of G instead of colorings and generalized Steingrimsson's theorem to signed graph colorings. Aaron is currently writing a joint paper with F. Breuer which will contain the results of his thesis. - Eric Etu (Computer Science) -- Computation of characteristic polynomials of hyperplane arrangements (SFSU Computer Science MA 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 (SFSU Mathematics MA 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 published a joint paper in the International Journal of Number Theory. - Mike Jackanich -- Antimagic graphs
We call a graph antimagic if we can distribute the numbers 1, 2, ..., n among its n edges such that the sums of the labels incident to each node are all different. A major open conjecture is that every graph except K2 is antimagic. (This conjecture is even still open for trees.) Let's call a graph weakly antimagic if it admits a similar labelling but with the relaxation that the labe ls--still chosen among the numbers 1, 2, ..., n--might not be distinct. Mike tries to prove that certain classes of graphs are weakly antimagic. - Curtis Kifer -- A special case of the Frobenius problem
Given relatively prime positive integers a1, a2, ..., an, the linear Diophantine problem of Frobenius asks for the largest integer that cannot be written as a nonnegative linear combination of a1, a2, ..., an. This problem is often called the coin-exchange problem because it can be rephrased as asking for the largest amount that cannot be changed using coins of denominations a1, a2, ..., an. The Frobenius problem is an old, famous, and wide open problem of combinatorial number theory, for which we have a closed solution for n=2, an algorithmic and generating-function solution for n=3, and many challenging fundamental open problems for n>3 (see Chapter 1 of my book with Sinai Robins). In a recent paper, Amitabha Tripathi solved the Frobenius problem in the special instance aj = b1b2...bj-1bj+1...bn, where b1, b2, ..., bn are fixed pairwise relatively prime positive integers. Curtis tries to apply Tripathi's methods to extensions of the Frobenius problem. - Asia Matthews -- A geometric approach to Carlitz-Dedekind sums (SFSU Mathematics MA 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 (SFSU Mathematics MA 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. - Chris O'Neill -- Unimodality of Order Polynomials (SFSU Mathematics BS May 09)
Order polynomials arise in the study of partially ordered sets, which are all over mathematics (Boolean lattices, divisor poset, face lattice of a polytope, etc.). Order polynomials are described with some basic properties in Chapter 7 of these lecture notes. My conjecture is that they are always unimodal (i.e., the coefficients go up and then down), except in special cases (in which we can compute these polynomials by hand). Chris computed many examples toward this conjecture. - 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. - Kim Seashore -- Growth series of root lattices (SFSU Mathematics MA 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. Kim wrote a paper based on her thesis (joint with F. Ardila, M. Beck, S. Hosten, and J. Pfeifle). - Andrew Van Herick -- Theoretical and Computational Methods for Lattice Point Enumeration in Inside-Out Polytopes (SFSU Mathematics MA 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. Andrew and I published a joint paper in Mathematics of Computation. - Whitney Zeldow -- Efficient bounds for unimodal Ehrhart h-vectors
In a recent paper, Alan Stapledon and I proved that certain rational generating functions connected with lattice-point enumeration in polytopes become unimodal (i.e., the coefficients of the numerator polynomial go up and then down) when a Hecke operator is applied. We proved that there exists a bound depending only on the degree of the rational function, from which point on we obtain unimodality. Whitney tries to come up with an efficient bound.
