1
$\begingroup$

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)$?

Improve this question
$\endgroup$
3
  • $\begingroup$ @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/… $\endgroup$
    – SagarM
    Commented Jun 22, 2023 at 13:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dmitry
    Commented Jun 22, 2023 at 14:09
  • 1
    $\begingroup$ So, basically, you are interested in Moment generating function for the number of triangles in Erdos-Renyi$(n, \frac 12)$. $\endgroup$
    – Dmitry
    Commented Jun 22, 2023 at 14:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.