TCS

SettingConfiguration : A configuration of graph is a map such as: \begin{aligned} \sigma: V &\to 2^V\\ u&\mapsto \{+,-\} \end{aligned}Partition Function: For graph , define its partition function as Z_G(\beta, \gamma, \lambda) = \sum_{\sigma} \beta^{m_{++}}\gamma^{m_{--}}\lambda^{n_+}where is the number of edges between two vertices pinned to , is the number of vertices pinned to , and we sum over all possible configurations. Initially, we wonder when there exsits a polynomial time ...