题目: ROUTING IN CYCLES VIA MATCHING

报告人:  喻革新 威廉玛丽学院

时间地点：6月6日下午4：00-5：00，教室：5104

摘要: Routing permutations on graphs via matching is an important problem proposed by Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (3) (1994), pp. 513--530], which has many applications in various different fields. Let $G$ be a graph whose vertices are labeled $1,\ldots,n$, and $\pi$ be a permutation on $[n] := \{1,2,\ldots,n\}$. A pebble $p_i$  that is initially placed at the vertex $i$ has destination $\pi(i)$ for each $i \in [n]$. At each step, we choose a matching and swap the two pebbles on each of the edges. The routing number $rt(G,\pi)$ for $\pi$ is the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang [SIAM J. Discrete Math., 24 (4) (2010), pp. 1482-1494] proved that $rt(C_n,\pi)\leq n-1$ for every permutation $\pi$ on the $n$-cycle $C_n$ and conjectured that  $rt(C_n,\pi)= n-1$ only if $\pi=(123\cdots n)$ or its inverse for $n\ge 5$. He, Valentin, Yin, and Yu proved the conjecture for all even $n \geq 6$. In this paper, we confirm the entire conjecture.  This is joint work with Xiangjun Li and Xia Zhang.

报告人简介：喻革新，美国威廉玛丽学院（College of William and Mary)教授。2006年毕业于伊利诺伊大学香槟分校（UIUC）获博士学位。2006-2008年在范得堡大学（Vanderbilt）做博士后研究。主要研究方向为图论，组合及其应用。主持完成多项美国NSF项目和NSA基金，并主持组织国际学术会议十余次，多次在国际学术会议做邀请报告。在图染色，图链接，图嵌入等方向发表SCI收录学术论文80余篇，其中在图论组合顶级期刊发表论文多篇，如J. Combin. Theory, Ser. B，Combinatorica，SIAM J. on Discrete Mathematics等。