  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 tighter upper bound on the independence number
$\alpha(\mathcal{B}_n)$ of $\mathcal{B}_n$, namely, we show that
$\alpha(\mathcal{B}_n) \le O(n!/1.97^n)$ improving on the previous known bound
of $\alpha(\mathcal{B}_n) \le O(n!/\sqrt{2}^{n})$ by [Kane-Lovett-Rao, FOCS
2017]. Our approach combines a higher-order version of their representation
theoretic techniques with linear programming. With an explicit construction, we
also improve their lower bound on $\alpha(\mathcal{B}_n)$ by a factor of $n/2$.
This construction is based on a proper coloring of $\mathcal{B}_n$, which also
gives an upper bound on the chromatic number $\chi(\mathcal{B}_n)$ of
$\mathcal{B}_n$. Via known connections, the upper bound on
$\alpha(\mathcal{B}_n)$ implies alphabet size lower bounds for a family of
maximally recoverable codes on grid-like topologies.
