A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank

Radu Curticapean, Nathan Lindzey, Jesper Nederlof

For even $k$, the matchings connectivity matrix ${\mathbf{M}}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al. (STOC 2013) showed that th…