Lower threshold ground state energy and testability of minimal balanced cut density

Abstract

Lovász and his coauthors defined the notion of microcanonical ground state energy ${\hat{\mathcal{E}}}_a(G,J)$ -- borrowed from the statistical physics -- for weighted graphs $G$, where $a$ is a probability distribution on $\{1,...,q\}$ and $J$ is a symmetric $q\times q$ matrix with real entries. We define a new version of the ground state energy, ${\hat{\mathcal{E}}}^c(G,J)={\inf }_{a\in A_c}{\hat{\mathcal{E}}}_a(G,J)$, called lower threshold ground state energy, where $A_c=\{a:a_i\ge c,i=1,\dots ,q\}$. Both types of energies can be extended for graphons $W$, the limit objects of convergent sequences of simple graphs. In the main result of the paper it is stated that if $0\le c_1<c_2\le 1$, then the convergence of the sequences $({\hat{\mathcal{E}}}^{c_2/q}(G_n,J))$ for each $J$ implies convergence of the sequences $({\hat{\mathcal{E}}}^{c_1/q}(G_n,J))$ for each $J$. As a byproduct one can derive in a natural way the testability of minimum balanced multiway cut densities, that is one of the fundamental problems of cluster analysis.

14 pages