## Permutations as product of parallel transpositions

**报告题目**：Permutations as product of parallel transpositions

**报告人**： Professor Gexin Yu (Department of Mathematics, College of Williams and Mary)

**时间**：2013年6月13日（星期四）16：30-17：30

**地点**：理科楼数学系B203

**摘要****: **Let 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.

**联系人：**崔建莲