MSRIUP 2012: Enumerative Combinatorics
Home  Research Topic  People  Colloquia  Research Projects 

Mixed graph coloring
Team: Taina JeanLouis, 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 kcolorings (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.

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.

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 somewhatdifferent 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.

Relatives of the Birkhoff polytope
Team: Gabriel DorfsmanHopkins, Joseph Pruitt and Jessica De Silva
A doublystochastic matrix is an n×nmatrix with nonnegative real entries, such that every row and column sums to 1. The set B_{n} of all such n×nmatrices is a nice convex object, called the n'th Birkhoff polytope. It's a hard and wideopen problem to compute the volume of B_{n}.There are various relatives of these polytopes; here is one example:Instead of nbyn permutation matrices, consider alternatingsign 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 CanfieldMcKay's asymptotic formula for the volume of B_{n}.

Threeterm theorems for Dedekindlike 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 threeterm 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 threeterm theorem for these generalizations, such as the three term theorem by M. Beck, C. Haase, and A. Matthews.

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 nowherezero 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 nowherezero 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 BeckZaslavsky, and ChenStanley.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.