How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?

Question

To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency matrix has determinant $\pm 3$.

Just to fix some basic facts and clarify the terminology:

1. A graph is cubic if every vertex has three neighbours
2. A graph is bipartite if the vertices can be partitioned into two sets $B$ (for black) and $W$ (for white) such that every edge connects a black vertex to a white one; this partition is unique if the graph is connected.
3. The bipartite adjacency matrix of a graph (with respect to a partition) is the matrix $A$ with rows indexed by black vertices, columns by white vertices and where $A_{bw} = 1$ if and only if $b$ is adjacent to $w$

This seems to involve two steps: finding out how many cubic bipartite graphs there are and then finding out what proportion of those have a bipartite adjacency matrix with the right determinant.

I can get some handle on the first step by looking at the tables produced by Canfield and McKay (hi Brendan!) at http://users.cecs.anu.edu.au/~bdm/data/semiregular.html who tell me that there are

$$Bv[20,3,20,3] = 77705104689340239554388061645133412621507133440000$$

semi-regular binary matrices with $20$ rows and $20$ columns where each row- and column-sum is equal to $3$.

Seeing I am only concerned with isomorphism classes, not total numbers, I can divide this enormous number by $2 \cdot (20!)^2$ to get an approximate number of about $6.56 \times 10^{12}$ for the number of isomorphism classes. (The number $2 \cdot (20!)^2$ is the number of distinct labelled graphs in the isomorphism class of a $40$-vertex cubic bipartite graph with trivial automorphism group and, up to a first approximation, all graphs have trivial group.)

Now for the second step - what proportion of these cubic graphs have a bipartite adjacency matrix with determinant of absolute value $3$? The determinant of any square regular binary matrix of degree $k$ (i.e. all row sums $k$, hence all column sums $k$) is a multiple of $k$ and so $\pm3$ are the smallest possible determinants of any non-singular matrix in this class.

I've done some experiments where, for each fixed number of vertices, I created a few million random cubic bipartite graphs of that size and then looked at what percentage have determinant $0$, $\pm 3$, $\pm 6$ and so on. I did this for graphs a bit smaller than, and a bigger than, the target size really just to see what happens.

The next table shows the number of vertices (expressed as a sum - so that $15+15$ means that each part of the bipartition has $15$ vertices for a total of $30$). The three numbers following are the percentage of graphs with determinant $0$, $\pm 3$ and $\pm 6$, with the numbers trailing off (not monotonically) as the determinant increases in absolute value. Here $d$ means $|\det A|$.

verts d = 0 d = 3 d = 6
15+15 61.41 00.00 00.00
16+16 35.67 14.07 16.94
17+17 33.22 13.80 15.41
18+18 52.97 00.00 00.00
19+19 30.79 10.44 14.11
20+20 28.91 09.89 12.92
21+21 45.35 00.00 00.00
22+22 26.39 07.67 11.30
23+23 24.87 07.11 10.22
24+24 38.46 00.00 00.00
25+25 22.44 05.58 08.78

So this suggests that around $10\%$ of the cubic bipartite graphs on $40$ vertices will have the right determinant, leaving me with something like $7 \times 10^{11}$ graphs, probably a bit more.

My question is really whether I can do better than this? Are there known counting results and/or determinant results that I can use to improve my two estimates?

Added in response to Brendan

If the matrices have order $3k \times 3k$, then the determinant must be a multiple of $9$, hence none of $\pm 3$, $\pm 6$.

To see, suppose that $A$ is such a matrix. Use elementary row operations to add rows $2$, $3$, $\ldots$, $3k$ to row 1. The top row is now all-$3$s, but the determinant is unchanged. Repeat the process with columns. Now we have a matrix where the $(1,1)$-entry is $9k$ and all the other entries in the first row and column are equal to $3$.

Consider now each transversal of the matrix, and the contribution to the determinant made by the product of the entries picked out by the transversal. If the transversal uses the $(1,1)$-entry then it automatically contributes some multiple of $9$, while if it doesn't then it must use the $(i,1)$ and $(1,j)$ entries for some $i$, $j \ne 1$ and as each of those values is equal to $3$, contribution is also a multiple of $9$.

Answer 1

You have a class of graphs closed under some notion of isomorphism, and a function $f$ defined on that class that is invariant under the same notion of isomorphism. For a graph $g$ let $a(g)$ be the order of its automorphism group, where automorphisms are isomorphisms of the same type from a graph to itself.

Fix a particular graph size (which fixes the supergroup that defines isomorphism). Let $g_1,\ldots,g_N$ be independent graphs from the uniform distribution for that size. Then $$ \frac{ \sum_{i=1}^N a(g_i) f(g_i) } { \sum_{i=1}^N a(g_i) } $$ is an estimator of the average of $f$ over isomorphism classes of graphs. It isn't an unbiased estimator, but it is asymptotically unbiased as $N\to\infty$.

In your case you want $f$ to be the characteristic function of the property of having determinant $\pm 3$, and you need to decide if you really want bipartite graphs rather than bicoloured graphs. The latter are a bit easier to generate uniformly at random.

Answer 2

A relevant comment, which the comment boxes cannot conveniently contain.

Summary. Briefly, the comment below gives, thanks to basic linear algebra and an easy theorem of Harary, a reformulation of your counting problem which I would call 'mildly combinatorial'. (It still involves a sum involving cancellation, and please note that I am not saying that the reformulation makes the counting easier.)

Note on notation. Please allow me to denote the biadjacency matrix by $B$ instead of '$A$', because I need the adjacency matrix too, which will be called $A$.

Details. If $G$ is any bipartite graph with bipartition classes of equal cardinality $s$, and if $A$ is its adjacency matrix, then, by basic linear algebra,

$\det(A) = (-1)^s\cdot \det(B)^2$

If $s$ is even (as in the OP, where $s=20$), then it follows that $\det(A)\geq0$.

If $\det(B)\in\{-3,+3\}$, as requested, then $\det(B)^2=\det(A)=9$. Conversely, if $\det(A)=9$, then $\det(B)\in\{-3,+3\}$. Therefore,

the problem in the OP is equivalent to counting the number of isomorphism classes of $3$-regular bipartite graphs with equally-sized classes of $20$ vertices each, whose adjacency matrix has determinant equal to $9$. (And to this one can apply Harary's result.)

For any graph $G$, a Sachs subgraph^(synonyms) of $G$ is an ordinary subgraph all of whose connected components are either circuits or edges. (Equivalently, it's a subgraph of minimum degree $\geq1$ and maximum degree $\leq2$; equivalently, it's a subgraph which is a union of two, not necessarily perfect, matchings.)

Let $\mathrm{evo}(H)$ denote the number of connected components of $H$ with an even number of vertices. ('evo' for 'even order'). Let $\mathrm{cir}(H)$ denote the number of connected components of $H$ which are circuits. By [H1962, p.208], it is known that

$\det(A) = \sum\limits_{H\in\textsf{AllSpanningSachsSubgraphs}(G)} (-1)^{\mathrm{evo}(H)}\cdot 2^{\mathrm{cir}(H)}$

So, what you are asking to be counted is

the number of isomorphism classes of balanced $3$-regular bipartite graphs $G$ on $40$ vertices such that $9 = \sum\limits_{H\in\textsf{AllSpanningSachsSubgraphs}(G)} (-1)^{\mathrm{evo}(H)}\cdot 2^{\mathrm{cir}(H)}$ $\hspace{35pt}$ (reformulation)

And of course you can 'filtrate' the problem by distinguishing integer-partitions of the number '9'.

I am well-aware that this does not appear to be any easier than what has been proposed already by other respondents. I call the above merely a semi-combinatorial interpretation, because there is still cancellation involved. This is by far not as clear and meaningful an interpretation as e.g. the interpretation of the minors in the well-known matrix-tree theorem. Still, in (reformulation) the determinant is gone.

${}$_________________________

^(synonyms)Synonyms of 'Sachs graph' in the literature are 'elementary subgraph', 'linear subgraph', and 'basic figure'.

[H1962] Frank Harary, The Determinant of the Adjacency Matrix of a Graph, SIAM Review, Vol. 4, No. 3. (1962), pp. 202-210.

Answer 3

Here is an approach I considered for a project many years ago. You might be able to use it for this.

A lot of it is computing partial isomorphisms, which I imagine is done well by nauty. Anyway, I will illustrate the first steps, which involves computing equivalence classes of isomorphic subgraphs of your graph set. Being more used to binary matrices, I will talk about the matrix version.

At each step we enumerate classes of r by 20 matrices of the desired form. We do whatever magic to reduce or represent the classes by as few representatives as possible, but this is important only to save runtime. I will start off with r=0, and one class representing all 0 by 20 allowed matrices.

Now for each class, generate all allowable next rows. For r=0, this will be 20 choose 3, or 1140 rows. Since I care only about isomorphism types, I end up with 1 class of 1140 equivalent representatives, and I choose a representative row which has three ones in the first three columns. I can move to r=1.

Now for each class, generate all allowable rows. Map all 2x20 candidates generated to a small set of representatives, and count how many each class represents. For the class with ones arranged in a two by three array, I get 1140, while for the representative that has only one one in the last seventeen columns, I get 51*1140. Of the four representatives, the one representing the largest class has three ones in columns four through six. Now for r=2.

For each of the four representatives from r=2, I generate possible allowed rows (still 1140) and then find those that are isomorphic, and count the number of individuals they represent. This if one representative of a 2 by 20 matrix belongs to a class of K many individuals, and it generates say five representatives of 3 x 20 matrices, those five represent at most 1140*K individual matrices. It may be fewer as some of the rows generated may lead to disallowed matrices. (For r=3, none are disallowed, but some of the 1140 candidates may be disallowed for larger r.)

The above is nothing new. It is just generating a lot of representatives of partly cubic bipartite graphs by drawing three lines from each of the first r black vertices, and then using whatever tool to find isomorphic members and combine them, while tracking class sizes. Here is the twist. Use Gram Schmidt orthonormalization on each representative.

When you do G-S, you can compute the partial volume of each representative in order to predict where the determinant is headed. Of course, if the class will represent a singular matrix , that tells the story for classes developed from that representative. If it has a large face, then it will require some further rows near but not quite in the span to keep the determinant small.

In brief, the idea is to predict the distribution of determinants by looking at all r row representatives and computing the distribution of the face volumes, while keeping track of how many members belong to the class for that representative. I imagine you can refine your prediction just by computing representatives up to r=10.

Gerhard "More Fun With Binary Matrices" Paseman, 2018.03.14.