Random-graph conjecture on square-free spanning-tree counts

Let \EuScriptG(n,p)\EuScript{G}(n,p) be a random simple undirected graph with nn vertices and edge-probability 0p10\leq p\leq 1. For c>1c>1, assume clog(n)/n<p(n)<1o(log(n)/n)c\log(n)/n<p(n)<1-o(\log(n)/n). Square-free complexity conjecture. As nn\to\infty, the probability that κ(\EuScriptG(n,p))\kappa(\EuScript{G}(n,p)) is square-free is (1o(1))6/π2(1-o(1))6/\pi^{2}. Since a connected undirected graph with square-free κ(G)\kappa(G) has cyclic (or trivial) critical group, this conjecture is intended to explain the preceding cyclicity prediction using the asymptotic density of square-free integers. Its status is not resolved in the source.

Sources & referencesView supporting material

Primary source

David G. Wagner, “The critical group of a directed graph”, arXiv:math/0010241 (2000).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.