A Unified Graph-Theoretic Framework for Free-Fermion Solvability

We provide a simple criterion to determine whether a spin model admits an exact description by noninteracting fermions. Our criterion is given in terms of the model's frustration graph, which captures the pairwise anticommutation relations between Pauli terms of the Hamiltonian in a given basis. An exact solution exists when this graph is claw-free and contains a structure called a simplicial clique. This unifies characterizations given in previous work, where it was shown that a free-fermion mapping exists when this graph is either a line graph, or (even-hole, claw)-free. The former case includes the Jordan-Wigner transformation and the exact solution to the Kitaev honeycomb model, and the latter case generalizes a non-local solution to the four-fermion model given by Fendley. Our characterization unifies these two approaches, extending the generalized Jordan-Wigner solutions to the non-local case and extending the generalized four-fermion solution to models of arbitrary spatial dimension. These results establish a deep connection between many-body physics and the mathematical theory of claw-free graphs.