数学科学系

Department of Mathematical Sciences

Permutations as product of parallel transpositions

报告题目Permutations as product of parallel transpositions

 

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

 

时间2013613(星期四)1630-1730

 

地点:理科楼数学系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.

 

联系人:崔建莲