12
$\begingroup$

Let $G$ be a connected, finite graph. (For me a graph is undirected, and it possibly has multiple edges, although the latter is not really crucial for this question). The complexity $c(G)$ (also known as the tree-number of $G$) is defined to be the number of spanning trees of $G$.

There is another number $k(G)$ that one can easily (and naturally?) associate to $G$. In all examples that I have studied, $k(G)$ equals $c(G)$, but I am not able to prove this in general.

The natural number $k(G)$ is defined to be the cardinalty of a certain set of functions $$\mathcal{F}(G) \subset \left\{ f \colon V(G) \to \mathbb{N}: \sum_{v \in V(G)} f(v) = b_1(G)\right\}\subset \mathbb{N}^{V(G)}$$ where $V(G)$ is the vertex set of $G$ and $b_1(G)$ is the first Betti number of $G$.

Here we construct all elements of $\mathcal{F}(G)$. Start by considering the constant zero function on all vertices of $G$. Then fix a spanning tree $\Gamma$ of $G$. For all edges $e$ that are missing from $\Gamma$ in $G$, add a $1$ to the function at exactly one of the two endpoints of $e$, and do this in all possible ways to obtain a set of functions $\mathcal{F}_{\Gamma}(G)$. Then $\mathcal{F}(G)$ is the union of all $\mathcal{F}_{\Gamma}(G)$, for $\Gamma$ that ranges over all spanning trees of $G$.

Here are two simple examples where it is immediate to check that $k(G)=c(G)$.

1) Take for $G$ the graph with two vertices $v_1,v_2$ connected by $k$ edges. The functions set $\mathcal{F}(G)$ constructed in the above paragraph consists of the assignments $$\{(k-1, 0), (k-2, 1), ... (0, k-1)\},$$ so $c(G)=k(G)=k$.

2) Take for $G$ the graph that is a planar $k$-gon (with $k$ vertices and $k$ edges). Here $\mathcal{F}(G)$ consists of functions that are constantly zero except for one vertex of $G$ where they equal $1$. Again we have that $c(G)=k(G)=k$.

Question: is it true that $k(G)=c(G)$ for all $G$?

Even if you do not know the answer, maybe you could point me to the relevant literature. Since I am not myself a graph theory expert nor a combinatorialist, this may very well be well-known or trivial in which case I do apologize.

$\endgroup$
  • $\begingroup$ If I understand the definition of $k(G)$, it depends only on the number of vertices, edges, and components of $G$. So it has no chance of always equaling the number of spanning trees. $\endgroup$ – Brendan McKay Aug 10 '16 at 10:57
  • $\begingroup$ No it does not: take the graph with three vertices and three edges $*=*-*$. For this we have $k(G)=c(G)=2$, but this graph has the same number of vertices and edges as the triangle graph, for which $k(G)=c(G)=3$. $\endgroup$ – calc Aug 10 '16 at 11:08
  • $\begingroup$ Maybe my definition of the set $\mathcal{F}(G)$ is not very clear? There are many functions there that are obtained in multiple ways. The union of the $\mathcal{F}_{\Gamma}$ is not a disjoint union. $\endgroup$ – calc Aug 10 '16 at 11:10
  • $\begingroup$ Apologies; I mistook a $\subset$ for an $=$. $\endgroup$ – Brendan McKay Aug 10 '16 at 11:43
  • $\begingroup$ Since you asked for relevant literature and said you're not an expert, here is this in case you don't know: en.wikipedia.org/wiki/Kirchhoff%27s_theorem $\endgroup$ – domotorp Aug 14 '16 at 21:00
10
+50
$\begingroup$

You're looking at the "integral break divisors" of the graph $G$. These were introduced by Mikhalkin and Zharkov. For a very clear presentation check out the paper "Canonical representatives for divisor classes on tropical curves and the Matrix-Tree Theorem" by An, Baker, Kuperberg, and Shokrieh, available online at https://arxiv.org/abs/1304.4259.

EDIT: I should say, the answer to your question is yes, the number of integral break divisors is always equal to the number of spanning trees of $G$, because these serve as canonical representatives of $\mathrm{Pic}^g(G)$.

$\endgroup$
  • 3
    $\begingroup$ By the way, in my opinion it would not be so easy to "stumble upon" these rather subtle objects (integral break divisors) so I'd be interested in what context they arose in your research. $\endgroup$ – Sam Hopkins Aug 15 '16 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.