Past masters thesis 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 (which he made freely available) 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 Sum_k=1...a-1 tan²(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.
• 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.
• 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.

Current masters thesis 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 (a_ij) and (b_ij) are orthogonal if the n² pairs (a_ij, b_ij) 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.
• Alex Plotitsa (Computer Science) -- 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 (arXiv:math.CO/0506315) 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 (joint project with Serkan Hosten)
  Let L be a lattice, and let M be a subset that generates L as a monoid. The coordination sequence (S_M(n))_n>=0 of (L,M) is given by S_M(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 G_M of L is the generating function of S_M(n): G_M(x) := sum_n>=0 S_M(n) xⁿ. Understanding growth series is fundamental to a lot of mathematical problems connected to lattices, for example in coding theory. In a recent paper (arXiv:math.CO/0508136), Serkan Hosten and I studied the growth series of cyclotomic lattices, based on unimodular triangulations of certain polytopes. Kim tries to extend these methods to lattices coming from classical root systems.
• Andrew Van Herick -- Flow polynomials of graphs
  A flow on a graph is an assignment from an abelian group A to the edges such that, given a fixed orientation of the graph, at each node the in-flow (the sum of the numbers on edges pointing towards the node) equals the out-flow (the sum of the numbers on edges pointing away from the node). A nowhere-zero flow is a flow which does not take on the value 0 on any edge. For A = Z_n, Tutte proved in the 40's that the number of nowhere-zero flows is a polynomial in n. Andrew tries to find out whether there is an interpretation of this polynomial at negative integers. (There are many polynomial counting functions that, originally defined for positive integers, have a pretty interpretation at negative integers. The most famous example is the chromatic polynomial of a graph G which, when evaluated, e.g., at -1, counts the number of acyclic orientations of G. Another example is the number of nowhere-zero Z-flows for which each assignment is bounded by n. Counting these flows again gives a polynomial at n, which at negative integers counts totally cyclic flows with some multiplicity. No such interpretation is known for A = Z_n.)

Possible future masters thesis projects

• Solid-angle polynomials
  The natural generalization of a two-dimensional angle to higher dimensions is called a solid angle. Suppose P is a convex rational polyhedron. The solid angle of a point x is a real number equal to the proportion of a small ball centered at x that is contained in P. When we sum the solid angles over all integer points in tP for an integral polytope P (i.e., the convex hull of finitely many integer points in R^d), we get a counting function in the integer parameter t that magically turns out to be a polynomial. Study properties of these solid-angle polynomials, initially by computing a lot of examples. Open problems include the question whether there exist solid-angle polynomials with negative coefficients and the conjecture that the numerator of the rational generating function of a solid-angle polynomial has always nonnegative coefficients, in analogy with a theorem of Stanley about the Ehrhart series of an integral polytope.
• Relatives of the Birkhoff polytope
  A doubly-stochastic matrix is an nxn-matrix with nonnegative real entries, such that every row and column sums to 1. The set of all such nxn-matrices is a nice convex object, called the n'th Birkhoff polytope. This polytope is the convex hull of the n-by-n permutation matrices. The latter, naturally, represent the symmetric group S_n. We can construct close relatives of the Birkhoff polytope by considering the convex hull of permutation matrices that correspond to a subgroup of S_n. Can anything be said about the volumes of those polytopes?
• Weakly 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 K₂ 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 labels--still chosen among the numbers 1, 2, ..., n--might not be distinct. Can you prove that certain classes of graphs are weakly antimagic?
• A special case of the Frobenius problem
  Given relatively prime positive integers a₁, a₂, ..., a_n, the linear Diophantine problem of Frobenius asks for the largest integer that cannot be written as a nonnegative linear combination of a₁, a₂, ..., a_n. 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 a₁, a₂, ..., a_n. 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 a_j = b₁b₂^...b_j-1b_j+1^...b_n, where b₁, b₂, ..., b_n are fixed pairwise relatively prime positive integers. Apply Tripathi's methods to extensions of the Frobenius problem.
• Enumeration of Golomb rulers
  A Golomb ruler is a set of integers a₁ < ... < a_n ("marks") such that all the differences a_j-a_k are distinct. For a given number n of marks, one is typically interested in finding the shortest Golomb rulers, where the length of a ruler is a_n-a₁. A related counting problem concerns the number of Golomb rulers as a function of the length (here n is fixed). By the theory of inside-out polytopes, this counting function is a quasipolynomial. Study these Golomb quasipolynomial.

"One of the big misapprehensions about mathematics that we perpetrate in our classrooms is that the teacher always seems to know the answer to any problem that is discussed. This gives students the idea that there is a book somewhere with all the right answers to all of the interesting questions, and that teachers know those answers. And if one could get hold of the book, one would have everything settled. That's so unlike the true nature of mathematics."
Leon Henkin

more pearls of wisdom