DMS Combinatorics Seminar

Speaker: Gexin Yu (William & Mary)

Title: Routing in cycles via matchings

Abstract: 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. Let \(rt(G,\pi)\), the routing number for \(\pi\), be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang proved that \(rt(C_n,\pi)\leq n-1\) for every permutation \(\pi\) on the \(n\)-cycle \(C_n\) and conjectured that for \(n \geq 5\), if \(rt(G,\pi)= n-1\), then \(\pi=(123\cdots n)\) or its inverse. He, Valentin, Yin, and Yu proved the conjecture for all even \(n \geq 6\). In this talk we will show how to prove the entire conjecture.  

This is joint work with Xiangjun Li and Xia Zhang.