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
    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
    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
    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
    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
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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