Searching for dense subsets in a graph via the partition function

Alexander Barvinok, Anthony Della Pella

For a set $S$ of vertices of a graph $G$, we define its density $0\le \sigma (S)\le 1$ as the ratio of the number of edges of $G$ spanned by the vertices of $S$ to $\left(\genfrac{}{}{0ex}{}{|S|}{2}\right)$.…