Randomized Approximation Schemes for the Tutte Polynomial and Random Clustering in Subdense and Superdense Graphs

arXiv2208.13809MaRDI QIDQ6409170FDOQ6409170

Authors: Mathias Hauptmann, Ronja Tiling 

Publication date: 29 August 2022

Abstract: Extending the work of Alon, Frieze abnd Welsh, we show that there are randomized polynomial time approximation schemes for computing the Tutte polynomial in subdense graphs with an minimal node degree of $Omegaleft(fracnsqrtlognight)$ . The same holds for the partition function $Z$ in the random cluster model with uniform edge probabilities and for the associated distribution $lambda(A),:AsubseteqE$ whenever the underlying graph $G=(V,E)$ is $ccdotfracnsqrtlog(n)$-subdense. In the superdense case with node degrees $n-o(n)$, we show that the Tutte polynomial $T_G(x,y)$ is asymptotically equal to $Q=(x-1)(y-1)$. Moreover, we briefly discuss the problem of approximating $Z$ in the case of $$-power law graphs.

This page was built for publication: Randomized Approximation Schemes for the Tutte Polynomial and Random Clustering in Subdense and Superdense Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409170)