Permutations as product of parallel transpositions

Title:  Permutations as product of parallel transpositions


Speaker:  Professor Gexin Yu (Department of Mathematics, College of Williams and Mary)


Time: 16:30-17:30 pm; June 13; 2013


Place: Conference Room B203, Department of Mathematical Sciences


AbstractLet G be a connected graph. Initially, each vertex $v$ of $G$ is occupied by a ``pebble'' that has a unique destination $\pi(v)$ in $G$ (so that $\pi$ is a permutation of the vertices of G). It is required that all the pebbles be routed to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected, and the pebbles at each edge’s endpoints are interchanged. Define $rt(G, \pi)$ to be the minimum number of steps to route the permutation $\pi$ and the routing number $rt(G)$ of $G$ to be the maximum of $rt(G,\pi)$ over all permutation $\pi$.

We will investigate two conjectures related to the routing numbers of graphs: Strang's conjecture on decomposition of permutation matrix with bandwidth b and Li-Lu-Yang's conjecture on extremal permutations on cycles.


Contact Jianlian Cui