Skip to content

The Inverse Spanning Tree Problem

June 24, 2009


What graphs have a given number of spanning trees

images

Gustav Kirchhoff is famous for his work on electrical circuits: his rules, called Kirchhoff’s laws, are widely used in electrical engineering. He also proved a theorem that allows the number of spanning trees to be computed, for any graph in polynomial time.

Today, I plan to talk about his famous spanning tree formula, which is often called the Matrix Tree Theorem. It arises in many places, and recently one of my graduate students, Farbod Shokrieh, has found a new interesting application. I was traveling the last few days and was in a meeting all day–each day–and {\dots} so this one will be shorter than usual.

Matrix Formula for Spanning Trees

The matrix tree formula is a truly remarkable theorem. We are so used to counting being hard, that it may come as a shock–if you have not seen it before–that there is an exact formula for the number of spanning trees. Moreover, the formula, since it is expressed as a determinant, can be computed exactly in polynomial time. Too bad Kirchhoff did not create a determinant formula for the number of colorings of a graph.

Let {G} be any graph, and let {A} be its adjacency matrix and {D} its degree matrix: the latter is the diagonal matrix with the vertex degrees on the diagonal. The Laplacian matrix of {G} is equal to {{\cal L}(G) = D-A}. The Kirchhoff theorem is stated as follows.

Theorem: The number of spanning trees of {G} is equal to the absolute value of any cofactor of {{\cal L}(G)}.

Recall, for any square matrix {M}, a cofactor is the determinant of the matrix that is obtained by deleting a row and column from {M}.

The Inverse Spanning Tree Function

The usual question that is studied, concerning spanning trees, is given a graph, how many spanning trees does the graph have? That is of course answered by the matrix theorem. However, we often want to know more information. A typical question might be: for this family of graphs what is the exact number of spanning trees as a nice formula; or if that is too hard, what is the approximate number of spanning trees?

Farbod’s research, which is joint with Matt Baker, concerns the structure of the Jacobian of a graph. The Jacobian is an abelian group that is associated with every undirected graph: the size of the Jacobian is equal to the number of spanning trees of the graph. I plan a more detailed post on this pretty research in the near future.

For now let’s just say that Farbod desires an answer to the following inverse problem: let {\kappa(S)} denote the number of vertices of the smallest graph that has exactly {S} spanning trees. Of course, {S} must be a non-zero natural number. We avoid {S=0} which arises from any disconnected graph. Thus, we put the “cart before the horse”–we give the number of spanning trees and ask for the graph. We want an inverse Kirchhoff matrix theorem, a theorem that tells us how to create a graph with a given number of spanning trees. This may be well known, but we do not know the answer–if you have it, we would be thrilled to hear from you.

Basic Properties of {\kappa(S)}

The first question is whether or not {\kappa(S)} is always well defined. More simply, given any {S>0}, is there at least one graph with that number of spanning trees? The answer is yes,

Theorem: For any positive natural number {S},

\displaystyle  \kappa(S) \le S.

Consider a cycle of {S} vertices. There are exactly {S} spanning trees, deleting each edge yields a distinct spanning tree. (Per comments, this needs {S \ge 3} to keep graph simple.)

In general, what is the behavior of the {\kappa } function? A simple property of this function is,

Theorem: For any {S,T}, the value of {\kappa(ST)} is at most

\displaystyle \kappa(S)+\kappa(T).

The proof of this is quite simple. Let {G_{S}} be a graph with {S} spanning trees, and let {G_{T}} be a graph with {T} spanning trees. Select a vertex {x} in {G_{S}}, and a vertex {y} in {G_{T}}. Then, create a new graph {H} that consists of {G_{S}} and {G_{T}} with one new edge joining {x} and {y}. Clearly, all spanning trees of {H} must use the new edge. However, any spanning tree of {G_{S}} and {G_{T}} form a unique spanning tree of {H}.

Primes

A fundamental problem, is how does the function grow? What numbers {S}, make {\kappa(S)} small, and which numbers {S} make the function large? These are the types of questions that Farbod needs to understand. A concrete example, is suppose that {p} is a prime, can {\kappa(p)} be small for prime {p}? By small he would like that

\displaystyle  \kappa (p) \le \log^{c}(p)

where {c} is a constant. Or failing that he would like that there are an infinite family of primes {p_{k}} and another number {m_{k}} polynomial in the size of {p_{k}}, so that

\displaystyle  \kappa (m_{k}p_{k}) \le \log^{c}(p_{k}).

We cannot resolve these questions, but can relate them to many other open number theory questions. There are some graphs, for which the number of spanning trees is known in a more convenient form. For example, for a fan on {n+1} vertices, the number of spanning trees is {F_{2n}} where {F_{m}} is the {m^{th}} Fibonacci number–see this pretty paper. A fan on {n+1} vertices consists of a line of {n} vertices, and one special vertex that connects to each vertex of the line: it looks a bit like a “fan.” (The figure is from the same paper.)
fan1

Theorem: Let {G} be the fan on {p+1} vertices, where {F_{p}} is prime. Then, {G} has {mF_{p}} spanning trees where {m} is at most polynomial in {F_{p}}.

The proof of the theorem depends on a simple fact about Fibonacci numbers.

\displaystyle  \mathsf{gcd}(F_{p},F_{2p}) = F_{p}.

From the above fact, it follows that {F_{2p} = m F_{p}}, for some {m}. And, we already know that the fan {G} has {F_{2p}} spanning trees. Also, note that {m} is bounded as claimed.

This theorem shows that, {\kappa(mF_{p}) \le p+1}. It is unknown currently whether or not {F_{p}} is prime for an infinite number of {p}, so the theorem may or may not be useful.

Open Problems

What can you say about the function {\kappa(S)}? Can it be small for {S} prime? More generally, is {\kappa(S)} always small? Note, a simple counting argument to try and prove a lower bound does not seem to work: the number of graphs on {n} vertices is exponential in {n}, so perhaps {\kappa(S)} is always polynomial in the size of {S}?

Finally, can we compute {\kappa(S)} in polynomial time?

About these ads
12 Comments leave one →
  1. June 24, 2009 10:40 pm

    Prof. Lipton,

    Is the Jacobian the same thing as the “critical group” of a graph (from chip-firing games)?

    • Farbod Shokrieh permalink
      June 25, 2009 11:21 am

      This group has appeared in the literature under many different names; in theoretical physics it was first introduced as the “abelian sandpile group” or “abelian avalanche group” in the context of self-organized critical phenomena. In arithmetic geometry, this group appeared as the “group of components” in the study of degenerating algebraic curves. In algebraic graph theory this group appeared under the name “Jacobian group” or “Picard group” in the study of
      flows and cuts in graphs. The study of a certain chip- firing game on graphs led to the definition of this group under the name “critical group”.

      When defined as critical group or sandpile group, the group law is quite “artificial”. That’s why I prefer to think of it as the “Jacobian”…

      • June 25, 2009 2:27 pm

        Is there a reference you can point me to for the “Jacobian” definition of this graph? I know a (very) little bit about the critical group, but haven’t seen these other definitions.

      • Farbod Shokrieh permalink
        June 25, 2009 3:54 pm

        Harrison: Here are the links:

        The lattice of integral flows and the lattice of integral cuts on a finite graph, by Bacher, La Harpe, Nagnibeda

        Algebraic Potential Theory on Graphs, by Biggs

        Riemann-Roch and Abel-Jacobi theory on a finite graph, by: Baker, Norine

  2. June 25, 2009 3:27 am

    I believe I learned about the Jacobian under the name “critical group”; if it’s isomorphic to the group I’m thinking of, it can be defined in terms of a chip-firing game with a sink being played on the graph.

    Anyway, this is a very interesting problem. You aren’t allowing multiple edges or loops, right?

    • Bart de Keijzer permalink
      June 25, 2009 5:43 am

      I think multiple edges are required in order to construct a graph with precisely 2 spanning trees.

    • rjlipton permalink*
      June 25, 2009 7:57 am

      Yes. It is the same as the chip firing game. I should have said that.

      Also for the inverse problem I believe that am mainly interested in simple graphs, i.e. no multiple edges or loops. Thus, I made an error when stated the theorem on all values are possible: the cycle would be degenerate if S was not more than 2.

  3. Anon permalink
    June 25, 2009 10:09 am

    Isn’t it true that if S=n^{n-2} (for some ineteger n), then k(S)=n, since the complete graph on n vetices has n^{n-2} spanning trees and any smaller graph has less than this many spanning trees? Doesn’t it mean that k(S)=logS/loglogS for infinitely many values of S?

    • rjlipton permalink*
      June 25, 2009 10:44 am

      Yes it does. But that says nothing about the value of k(S) for general S. Right? The interesting case is what is k(p) where p is a prime.

  4. Ralph Hartley permalink
    June 29, 2009 8:15 am

    Here are the first 500 values except for S in {13,22,34,38,47,107,122,218,466,475}, which are all 10 or more. The values for 0 and 1 depend on the exact wording of definitions. Except for 475, all the values greater than 9 are primes or two times a prime.
    These were produced by brute force. It might be possible to check graphs
    with 10 or more nodes, but it would require more optimization.

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
    =========================================================================================
    00 | 2 0 Inf 3 4 5 6 7 4 5 10 5 5 >9 6 6 4 7 8 7
    20 | 5 5 >9 8 5 9 8 7 6 6 6 9 6 7 >9 6 6 7 >9 7
    40 | 5 7 8 7 7 5 7 >9 6 7 7 7 6 8 6 6 6 8 8 8
    60 | 6 6 9 7 6 8 6 8 7 6 8 9 7 7 9 5 7 9 9 7
    80 | 7 6 7 9 7 7 9 7 7 7 7 7 8 7 7 7 6 8 7 6
    100 | 6 7 8 8 6 7 8 >9 8 8 7 6 7 8 6 6 8 7 8 8
    120 | 6 6 >9 9 7 5 8 8 6 8 6 8 7 8 8 6 7 8 8 7
    140 | 7 7 8 9 7 8 9 8 7 8 9 7 7 7 7 7 7 9 9 7
    160 | 7 8 7 7 9 7 7 9 7 7 9 7 7 9 9 7 7 7 7 8
    180 | 6 7 9 7 7 6 8 7 8 7 7 7 6 9 7 7 7 9 8 7
    200 | 6 8 9 8 7 7 9 7 8 6 8 8 8 8 8 8 6 9 >9 9
    220 | 8 8 8 8 6 6 8 8 8 8 8 7 8 8 8 8 7 8 8 8
    240 | 7 8 7 7 8 7 8 8 7 8 8 8 8 8 9 7 7 7 8 8
    260 | 7 8 8 8 7 8 8 8 8 8 8 8 7 7 9 7 7 8 7 7
    280 | 8 7 9 8 7 7 8 7 7 7 8 7 8 8 8 8 7 7 9 7
    300 | 6 8 9 8 8 7 8 8 7 8 9 9 8 7 8 7 9 9 8 8
    320 | 7 7 9 7 6 7 7 7 8 7 7 9 8 8 8 7 6 9 7 7
    340 | 7 8 8 9 7 7 9 9 8 9 8 7 7 7 7 7 8 9 9 9
    360 | 6 7 9 8 8 9 9 9 7 8 9 9 7 9 8 7 8 7 8 9
    380 | 8 9 9 8 6 7 7 9 8 8 8 8 7 8 8 8 8 9 8 7
    400 | 7 8 8 9 8 8 9 8 7 8 8 8 8 8 9 8 8 8 8 8
    420 | 7 9 8 8 8 7 9 8 8 7 8 8 7 8 9 8 8 8 8 8
    440 | 7 7 9 8 7 8 9 8 7 8 8 7 8 8 8 7 7 8 8 8
    460 | 8 9 8 8 8 7 >9 8 8 8 8 8 7 8 8 >9 8 8 8 8
    480 | 7 8 8 8 8 7 8 8 8 8 8 8 8 8 8 8 8 7 8 8

  5. Jernej permalink
    June 29, 2009 10:42 am

    This problem is very neat!

    Another thing one could try to find out is wheather there is any lower bound for k(S)..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,554 other followers