It is generally believed that, for physical systems in the thermodynamic limit, the microcanonical description as a function of energy coincides with the canonical description as a function of temperature, the original argument being that in the canonical ensemble at fixed temperature the energy fluctuations are negligible with respect to the average energy. Today, most textbooks in statistical physics still convey the message that the equivalence of ensembles holds universally for every physical system; however, various examples have been identified for which the microcanonical and canonical ensembles are not equivalent (e.g. for certain many-body systems encountered in models of fluid turbulence, quantum phase separation, etc.).

Here we show that ensemble nonequivalence can manifest itself also in discrete enumeration problems. We argue that, for any enumeration problem where we need to count microcanonical configurations compatible with a given constraint, there exists a dual problem involving canonical configurations induced by the same constraint. We then prove a general result showing that, for discrete systems, ensemble equivalence reduces to equivalence of the large deviation properties of microcanonical and canonical probabilities of a single microstate. As specific examples, we consider ensembles of networks with topological constraints. We find that, while graphs with a given number of links are ensemble-equivalent, graphs with a given degree sequence (including random regular graphs, sparse scale-free networks, and core-periphery networks) are not. We also find that, as the heterogeneity of the degree distribution increases, the violation of non-equivalence gets more severe.

Our proof of the breakdown of ensemble equivalence in graphs with given degree sequence provides a theoretical explanation for some recent observations, namely the fact that the canonical and microcanonical entropies of random regular graphs are different even in the thermodynamic limit and the non-vanishing of canonical fluctuations in the configuration model.