Tighter Bounds on the Independence Number of the Birkhoff Graph

Leonardo Nagami Coregliano, Fernando Granha Jeronimo

The Birkhoff graph ${\mathcal{B}}_n$ is the Cayley graph of the symmetric group $S_n$, where two permutations are adjacent if they differ by a single cycle. Our main result is a tigh…