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

Abstract. Lovász and his coauthors in [4] defined the notion of microcanonical ground state energy \(\hat{\mathcal{E}}_\mathbf{a} (G,J)\) — borrowed from the statistical physics — for weighted graphs \(G\), where \(\mathbf{a}\in \mathrm{Pd}_q\) 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\limits_{\mathbf{a}\in A_c}\hat{\mathcal{E}}_\mathbf{a} (G,J)\), called lower threshold ground state energy, where \(A_c = \{\mathbf{a}\in \mathrm{Pd}_q \colon \, 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. The main result of the paper is Theorem 3.2 stating that if \(0\leq c_1 < c_2 \leq 1\), then the convergence of the sequences \((\hat{\mathcal{E}}^{c_2/q} (G_n,J))_{n\geq 1}\) for each \(J \in {\mathrm{Sym}}_q\) implies convergence of the sequences \((\hat{\mathcal{E}}^{c_1/q} (G_n,J))_{n\geq 1}\) for each \(J \in {\mathrm{Sym}}_q\). As a byproduct one can derive in a natural way the testability of minimum balanced multiway cut densities — one of the fundamental problems of cluster analysis — proved in [2].