9
$\begingroup$

In thinking about constructing manifolds via surgery or plumbing, the following combinatorial problem comes up:

If T is a tree with adjacency matrix A and I is the identity matrix of the same order, when is |det(A-I)| = 1 possible? The fact that this is true for the E8 tree allows us to construct manifolds following Milnor et al. I've thought about this problem a bit and can't see an obvious reduction to similar problems, involving root systems, etc. Can it be shown that no other examples exist? What simple argument am I missing?

A correction after the comments I got below - I originally put |det(A-I)|=1 but actually meant |det(A+2I)|=1 or equivalently |det(A-2I)|=1 since trees are bipartite and their eigenvalues are symmetric around 0. Chris's observation is interesting as well... I now have to go back and do some rechecking of small trees. ::::grin::::

Improve this question
$\endgroup$
5
  • $\begingroup$ My apologies, I made a mistake. I realized this after seeing the comment by @Chris Godsil. The relevant condition I want is \det(A-I)=\pm1. Given any tree is bipartite, \det(A-2I)\ would work as well. It is interesting that so many trees have \det(A-I)=\pm1, though. $\endgroup$
    – Mike
    Commented Jan 12, 2014 at 19:27
  • $\begingroup$ Problems with MathJax and formatting here. I've added a correction/addition to my original post. $\endgroup$
    – Mike
    Commented Jan 12, 2014 at 19:42
  • 1
    $\begingroup$ Since $\det(A+2I)$ has the same parity as $\det(A)$, to have $\det(A+2I)=\pm1$ you need the tree to have a perfect matching (and so the number of vertices must be even). I found one tree that works on 10 vertices, none on 12 or 14. $\endgroup$
    – Chris Godsil
    Commented Jan 12, 2014 at 20:42
  • 1
    $\begingroup$ Also none on 16 vertices but then, strangely, a whole bunch on 18 vertices (in fact, 18 of them). Here's the first of them in g6 notation suitable for direct import into sage: Q??????_A?C?C?a?G_?S?Go?So? $\endgroup$
    – Gordon Royle
    Commented Jan 13, 2014 at 7:12
  • $\begingroup$ Not particularly on target but: It is a standard lemma that the disjoint unions of the ADE Dynkin diagrams are the only graphs with $A+2 I$ positive definite, and $E_8$ is the only one of those with determinant $1$. $\endgroup$
    – David E Speyer
    Commented Jan 15, 2014 at 0:33

3 Answers 3

Reset to default
4
$\begingroup$

According to sage, there are 7 trees (out of 23) on 8 vertices with $\det(A-I)=\pm1$ and 20 (out of 47) on 9 vertices. So it seems that the condition is satisfied easily.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Chris, thanks for your response. I wasn't aware that Sage had code generating small trees and their invariants easily(me bad). I'll have to do some computations. Also, I made a mistake, see my new comment above. $\endgroup$
    – Mike
    Commented Jan 12, 2014 at 19:25
4
$\begingroup$

Using sage, and up to 16 vertices included, one finds only two trees satisfying $|det(A+2I)|=1$, namely $E_8$ and $E_{10}$.

EDIT: I also confirm that there are 18 such trees with 18 vertices. Here they are in the graph6 string notation (suitable for input in sage):

['Q??GOGA?O??C?AGAA?C???@d?O_',  'Q??GOGA?O@?A?A?@G?C??G?gO@O',
 'Q???GGA?O@??_?O?C???kC@OGG_',  'Q???GGA?O??C_AO?C???oC@OG?o',
 'Q??GOGA?O??C?C?AG@C??G@COB?',  'Q???G???OG?COCGAO??F?C?GGCG',
 'Q????CA??O?_O?G??AO@aCPA?G_',  'Q????CA?O?O?O?G??D_GaCA?GAG',
 'Q???GGA?O@???@_?G??OSG@OOO_',  'Q???GGA??A?A?GGCO?A??A?cOK_',
 'Q???GGA??A?A?GOCO??ODGA?OCG',  'Q????G??_??@OGGOO??L?CE?GC_',
 'Q????C???Q?_O?G??AO@aCHAA?_',  'Q????C???_@G@GO??AG@_G_E?G_',
 'Q????_G@?C???B_?G?H?`?P??`G',  'Q???G??@?C?GOGG?O??BACCGGK?',
 'Q????GA????@?DG?A@?OBOKA@@?',  'Q????GAA???@?C_?G?G_HGQ??b?']

For example, you can type Graph('Q????GAA???@?C_?G?G_HGQ??b?') to get the last one.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The OP seems to be interested in concrete examples. Maybe it would be useful to him if you could list those 18 trees. $\endgroup$
    – André Henriques
    Commented Jan 15, 2014 at 14:07
1
$\begingroup$

What about $A_p$, $p\ne2\bmod 3$? It looks like you are considering the graph lattice with weights of the vertices equal to $-1$, and you want the result unimodular. There are lots of such graphs; the very first thing one can see is that one can always extend any leaf by~$3$. For the classification, try to mimic blow-down of $(-1)$-curves, i.e., splitting off orthogonal summands generated by vectors of square $(-1)$. In fact, this is done somewhere (in conjunction with plumbings), but I do not remember the reference :(

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .