MSRI-UP 2012: Enumerative Combinatorics

1. Mixed graph coloring

   
   Team: Taina Jean-Louis, Joseph Crawford and Daniel Blado
   
   

   A mixed graph is a graph with both directed and undirected edges. Mixed graphs come with a (strong) chromatic polynomial and a weak chromatic polynomial; in both cases we count k-colorings (such as with the chromatic polynomial for ordinary graphs) that have to assign different colors to vertices connected by an undirected edge, for directed edges the colors have to obey the > (in the strong case) or >= (in the weak case) relation as we move along the edge. M. Bekc, T. Bogart, and T. Pham proved a reciprocity theorem for strong chromatic polynomials. We will try to come up and prove a reciprocity theorem for weak chromatic polynomials. Furthermore, we will try to use the connection found by H. Furmanczyk, A. Kosowski, B. Ries, and P. Zylinski to obtain a reciprocity theorem for edge colorings of mixed graphs.
    

2. Chromatic polynomials of signed Petersen graphs

   
   Team: Alana Shine, Erika Meza and Bryan Nevarez

   
   T. Zaslavsky proved that there are essentially six signed versions of the famous Petersen graph. (Look here for an introduction to signed graphs.) He conjectures that they all have different chromatic polynomials. We will try to compute the latter, e.g., using A. Van Herick's IOP software.
    

3. Shi arrangements, parking functions, and mixed signed graphs

   
   Team: Schuyler Veeneman, Claudia Rodriguez and Michael Dairyko

   
   The Shi arrangement is a famous hyperplane arrangement, and its regions are in bijection with parking functions; there are two somewhat-different proofs of this bijection, one by I. Pak and R. Stanley and one by C. Athanasiadis and S. Linusson. The first bijection can be realized by a model involving orientations of certain mixed graphs. The first goal of our project is to establish this realization thoroughly (i.e., mathematically sound). The second goal is to generalize it to signed graphs, in the hope that this will shed additional light onto the main result in this recent paper by K. Meszaros; see also this even more recent paper of D. Armstrong, V. Reiner, and B. Rhoades.
    

4. Relatives of the Birkhoff polytope

   
   Team: Gabriel Dorfsman-Hopkins, Joseph Pruitt and Jessica De Silva

   
   A doubly-stochastic matrix is an n×n-matrix with nonnegative real entries, such that every row and column sums to 1. The set B_n of all such n×n-matrices is a nice convex object, called the n'th Birkhoff polytope. It's a hard and wide-open problem to compute the volume of B_n.There are various relatives of these polytopes; here is one example:Instead of n-by-n permutation matrices, consider alternating-sign matrices. Their convex hull is a polytope which was recently studied by J. Striker.We will explore if anything be said about the volumes of these polytopes, e.g., some analogues of Canfield-McKay's asymptotic formula for the volume of B_n.
    

5. Three-term theorems for Dedekind-like sums

   
   Team: Chelsie Norton, Jordan Clark and Stefan Klajbor

   
   Dedekind sums are finite arithmetic sums with many applications in number theory, discrete geometry, topology, computer science, and other areas. (For an introduction see, e.g., Chapter 8 in this book.)A famous paper by J. Pommersheim contains a three-term reciprocity law for the classical Dedekind sum. K. Girstmair explained Pommersheim's theorem by proving a link to two older theorems of Dedekind and Rademacher. There are many generalizations of Dedekind sums (some families are summarized here and here); the goal of our project is to find analogues of Pommersheim's three-term theorem for these generalizations, such as the three term theorem by M. Beck, C. Haase, and A. Matthews.
    

6. Multivariate flow and tension polynomials of graphs

   
   Team: Gordon Kirby, Molly Stubblefield and Alyssa Cuyjet

   
   Flows and tensions of graphs are somewhat analogous to colorings, but one labels edges. Let's be more precise.Given a graph, orient it (i.e., give each edge an orientation) in some arbitrary but fixed way. A flow is a labelling of the edgessuch that at each node v, the sum of the labels at edges pointing towards v equals the sum of the labels at edges pointing away from v.A tension is a labelling of the edges such that the sum of the labels on any cycle of the graph (taken with signs given by theorientations of the edges of the cycle) is zero.One is typically interested in nowhere-zero flows and tensions, i.e., we're not allowed to use the label 0 anywhere.Some fairly recent theorems of Kochol and Chen say that if the flow/tension labelsare integers between -k and k, the number of nowhere-zero flows/tensions is a polynomial in k.Moreover, there are interpretations of these polynomials when they are evaluated at negative integers; these are reciprocity theorems due to Beck-Zaslavsky, and Chen-Stanley.We will try to generalize these counting functions to the multivariable case, i.e., for each edge e, we are allowed to use labelsbetween -k_e and k_e, for some given values k_e.Now the flow and tension counting functions depend on several variables k_e (one for each edge of the graph). We will study these counting functions.