The Spectral Gap of Graphs Arising From Substring Reversals

[摘要] The substring reversal graph $R_n$ is the graph whose vertices are the permutations $S_n$, and where two permutations are adjacent if one is obtained from a substring reversal of the other. We determine the spectral gap of $R_n$, and show that its spectru

[学科分类] 离散数学和组合数学

[关键词] Spectral graph theory;Pancake flipping;Prefix reversal