ROUTING IN CYCLES VIA MATCHING

ROUTING IN CYCLES VIA MATCHING

Details

  • Time: 4:00-5:00 pm   (Beijing Time)
  • Date: Wednesday, June 12, 2024
  • Venue: MA305
  • SPeaker: Prof. Gexin Yu
  • Language:英语

Abstract

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, . . . , n, and π be a permutation on [n] := {1, 2, . . . , n}. A pebble pi that is initially placed at the vertex i has destination π(i) for each i ∈ [n]. At each step, we choose a matching and swap the two pebbles on each of the edges. The routing number rt(G, π) for π 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(Cn, π) ≤ n − 1 for every permutation π on the n-cycle Cn and conjectured that rt(Cn, π) = n − 1 only if π = (123 · · · n) or its inverse for n ≥ 5. He, Valentin, Yin, and Yu proved the conjecture for all even n ≥ 6. In this paper, we confirm the entire conjecture. This is joint work with Xiangjun Li and Xia Zhang.

Speaker

Gexin Yu is a Professor and Chair of the Department of Mathematics at the College of William and Mary. His primary research interests include graph theory, combinatorics, and their applications. Prof. Yu obtained his Ph.D. from the University of Illinois at Urbana-Champaign in 2006. He was a postdoctoral researcher at Vanderbilt University from 2006 to 2008 and then joined the College of William and Mary in 2008.

He has been the principal investigator for numerous NSF and NSA grants and has hosted over ten international conferences. Additionally, he has been an invited speaker at many international conferences. Prof. Yu has published more than 80 papers on graph coloring, graph linkage, and graph embedding. Notably, he has contributed many papers to top journals in graph theory and combinatorics, including the Journal of Combinatorial Theory Series B, Combinatorica, Journal of Graph Theory, and SIAM Journal on Discrete Mathematics.