MSRI-UP

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 -ke and ke, for some given values ke.Now the flow and tension counting functions depend on several variables ke (one for each edge of the graph). We will study these counting functions. 

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.

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 coloringsof mixed graphs.

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.

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.

A doubly-stochastic matrix is an n×n-matrix with nonnegative real entries, such that every row and column sums to 1. The set Bn 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 Bn.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 Bn.