Exact Results on Itinerant Ferromagnetism and the 15-puzzle Problem

We apply a result from graph theory to prove exact results about itinerant ferromagnetism. Nagaoka's theorem of ferromagnetism is extended to all non-separable graphs except single polygons with more than four vertices by applying the solution to the generalized 15-puzzle problem, which studies whether the hole's motion can connect all possible tile configurations. This proves that the ground state of a U→∞ Hubbard model with one hole away from the half filling on a 2D honeycomb lattice or a 3D diamond lattice is fully spin-polarized. Furthermore, the condition of connectivity for N-component fermions is presented, and Nagaoka's theorem is also generalized to SU(N)-symmetric fermion systems on non-separable graphs.