Monday, September 18th, 2017 4pm-5pm Burnside 1205
Computing the rank of configurations on graphs

The paper by M. Baker and S. Norine [1] in 2007 introduced a new pa- rameter in Graph Theory it was called the rank of configurations on graphs. A configuration consists of giving an integer (positive or negative) value to each vertex of the graph. Two configuration are equivalent if one can be obtained from the other by adding rows of the Laplacian matrix of he graph. The rank gives a measure of the distance between a positive configuration and the set of configurations not equivalent to a positive one. It was proved 8 years after that the computation of the rank is an NP-complete problem for general graphs. In a paper written with Yvan Le Borgne we presented a greedy algorithm computing an upper bound for the rank in polynomial time. For configurations in the complete graph this algorithm works in linear time and gives an exact value for it. In this talk we present this algorithm and show how it uses some central objects in Combinatorics like Dyck paths and Parking functions.

Fall 2017 Schedule