Home | Research Topic | People | Colloquia | Research Projects | Application Information | Pictures |

### Mixed graph coloring

Taina Jean-Louis, Joseph Crawford and Daniel Blado

Team:

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.

### Chromatic polynomials of signed Petersen graphs

Alana Shine, Erika Meza and Bryan Nevarez

Team:

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

Schuyler Veeneman, Claudia Rodriguez and Michael Dairyko

Team:

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.

### Relatives of the Birkhoff polytope

Gabriel Dorfsman-Hopkins, Joseph Pruitt and Jessica De Silva

Team:

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

### Three-term theorems for Dedekind-like sums

Chelsie Norton, Jordan Clark and Stefan Klajbor

Team:

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.

### Multivariate flow and tension polynomials of graphs

Gordon Kirby, Molly Stubblefield and Alyssa Cuyjet

Team:

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.