34
$\begingroup$

This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.

The determinant of a simple graph is the determinant of its adjacency matrix which is, of course, a symmetric binary matrix with zero-diagonal.

Question: Which graph has the largest value of $|\det(A)|$ over all simple undirected graphs on $n$ vertices?

(We could ask separately for the graphs with minimum determinant, which will be some negative number, and those of maximum determinant, but by taking the absolute value, this just becomes a question of which graphs have the most extreme determinant.)

For small numbers of vertices, we can just find the answer almost by hand:

  • On $2$ vertices, the winner is the complete graph $K_2$ with spectrum $\{-1,1\}$, so determinant $-1$, of absolute value $1$.
  • On $3$ vertices, the winner is $K_3$ which has absolute value of determinant equal to $2$
  • On $4$ vertices, the winner is $K_4$ with value $3$.
  • On $5$ vertices, there are two winners (both with value $4$), namely $K_5$ and the "bowtie" graph (two triangles sharing a common vertex).

Sequence so far is $1$, $2$, $3$, $4$ (don't bother looking this up in OEIS).

For larger numbers of vertices, we turn to the computer and discover that on $6$ vertices, the maximum value is $7$, and this is realised by two graphs, namely a triangle and a $4$-clique sharing a vertex, and two $4$-cliques sharing an edge.

From there, the sequence continues: 12, 28, 128, 256, 576 for 7, 8, 9, 10 and 11 vertices respectively, with between 2 and 7 graphs achieving the maximum for each of these values.

So now I do have enough to look up in the OEIS, but there are no matches.

The problem of finding the maximum determinant of a (0,1)-matrix, often called the Hadamard maximal determinant problem has been extensively studied, and there are lots of bounds, and constructions of extremal matrices etc. (There is a mapping between (0,1)-matrices and (-1,1)-matrices which changes the determinant predictably and when they exist, Hadamard matrices are the winners.)

So lots is known, and it is summarised in sequence A003432 on the OEIS which gives exact values up to $n=20$.

Just for comparison, for $n = 6$ to $n=11$, we have

  • 7, 12, 28, 128, 256, 576 (for graphs)
  • 9, 32, 56, 144, 320, 1458 (for (0,1)-matrices)

From several sources, including the OEIS, I have been advised to check a website attributed to Will Orrick at http://www.indiana.edu/~maxdet/ but this appears to be offline or removed or something, and nor could I find his email address in the directory for that university.

So my question remains: what is known about maximal determinant (in absolute value) of the adjacency matrix of a simple graph on $n$ vertices?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ You can often try the internet wayback machine when a page is down. In this case, it works and you can check an old version of Will Orrick's site at: web.archive.org/web/20160229005938/http://www.indiana.edu/… (Feb 29 2016) and a few other dates if you wish. $\endgroup$
    – Asvin
    Mar 11, 2021 at 19:28
  • 3
    $\begingroup$ It's at least exponential by taking $\lfloor n/s\rfloor$ disconnected copies of $K_s$ to get a det of $\pm (s-1)^{\lfloor n/s\rfloor}$ (which is about $1.3^n$ for $s=4,5$). An another condition you might add is connectedness. $\endgroup$
    – rikhavshah
    Mar 12, 2021 at 3:17
  • $\begingroup$ And an interesting question might be: which are the external graphs with the highest (or for that matter: lowest) symmetry, in terms of size of automorphism groups? $\endgroup$
    – Wolfgang
    Mar 16, 2021 at 17:50
  • 4
    $\begingroup$ If $n$ is a prime power of the form $4k+1$ then the Paley graph <en.wikipedia.org/wiki/Paley_graph> has determinant has determinant $2k^{2k+1} = 2^{-n} (n-1)^{(n+1)/2}$; this grows faster than exponentially, and is within a factor of about $2^n$ of the upper bound $n^{n/2}$ from Hadamard's inequality <en.wikipedia.org/wiki/Hadamard%27s_inequality>. It's probably even closer to optimal than that because each row of $A$, though possibly of norm as large as $\sqrt n$, is within $\frac12 \sqrt n$ of the $1$-dimensional space spanned by $(1,1,1,\ldots,1)$. $\endgroup$
    – Noam D. Elkies
    Mar 17, 2021 at 4:36
  • $\begingroup$ According to mathoverflow.net/users/484/will-orrick Will Orrick was last seen here yesterday. He maintains a Maximal Determinant Blog at willorrick.wordpress.com $\endgroup$
    – Gerry Myerson
    Mar 17, 2021 at 5:51

1 Answer 1

Reset to default
3
$\begingroup$

This may not be responsive, but I think it's amusing. I apologize in advance. To get an order 16 graph with determinant 327680 begin with (a) the line graph of $K_5$, (b) $K_5$, and (c) an isolated point. Join all vertices in (a) to (c) and no vertices in (b) to (c). Join each vertex in (b) to a maximum clique [of size 4] in (a).

The graph6 format is: OV`vfmlJJNhRVDmdzkUVX

Improve this answer
$\endgroup$
3
  • $\begingroup$ One can play with this graph and get (graph6 format) PxWTslT{nWNlqxQkpxX{rpM[ with determinant 819200, a little more than Paley(17) which has 524288. After that, improving on Paley graphs may be difficult. $\endgroup$
    – Yoozer2021
    Mar 17, 2021 at 12:09
  • $\begingroup$ Nice one, I like the graph that beats the Paley graph... that would be a good place to start for a better infinite family. $\endgroup$
    – Gordon Royle
    Mar 17, 2021 at 13:37
  • $\begingroup$ This sounds like the complement of the Clebsch graph. It has the same determinant. $\endgroup$
    – Geoffrey Exoo
    Apr 3, 2021 at 3:07

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.