# Is there a known FPRAS for this simple partition function?

I Let $$G$$ be the set of simple graphs on $$n$$ nodes. Given a $$g \in G$$, we denote the number of triangles in $$g$$ with $$n(g)$$. Given some positive real-valued parameter $$w$$, we define the the function $$Z(w)$$ as follows: $$Z(w)= \sum_{g}\exp(w\cdot n(g))$$

I think its an intractable problem to compute $$Z(w)$$, but I don't know about approximations. Is there a known FPRAS for computing $$Z(w)$$?

• @InuyashaYagami Partition function is a bad name here inspired from physics/statistics/Machine Learning. But it does not matter, I have edited the question to just have it as $Z(w)$. But if you are interested: en.wikipedia.org/wiki/… Commented Jun 22, 2023 at 13:42
• I assume that $G$ is the set of all simple undirected graphs on $n$ nodes. I didn't find the solution, but maybe the following will help. It suffices to know the distribution of the number of triangles in an Erdos-Renyi graph with $p= \frac 12$. Basically, something like stats.stackexchange.com/questions/338267/…, but you need to know the whole distribution. Commented Jun 22, 2023 at 14:09
• So, basically, you are interested in Moment generating function for the number of triangles in Erdos-Renyi$(n, \frac 12)$. Commented Jun 22, 2023 at 14:24