Number of bipartite graphs with full rank
Roland Bacher
Roland.Bacher at ujf-grenoble.fr
Fri Nov 11 16:35:39 CET 2005
On Fri, Nov 11, 2005 at 12:48:22PM -0000, simone at cs.york.ac.uk wrote:
> Dear seqfans,
>
> I have the following question:
>
> What is the number of nonisomorphic bipartite graphs on n vertices whose
> adjacency matrix has n nonzero eigenvalues?
>
> Thanks a lot for your time,
> Simone
>
> --
> Simone Severini
> Department of Mathematics and Department of Computer Science
> University of York, YO10 5DD York, U.K.
> Tel: +44 (0)1904 433072
> Web: www-users.york.ac.uk/~ss54
>
>
A necessary condition is that $n$ is an even integer $n=2m$
and each class of vertices has exactly $n$ elements. Indeed,
the adjacency matrix of such a graph with suitably ordered
vertices is given by
( 0 A )
( A^t 0 )
and such a matrix is non-degenerate if and only if
$A$ is a non-degenerate square matrix.
The total number of such graphs with $2m$
vertices equals thus the number of orbits of
non-degenerate {0,1} matrices of square-size m\times m
under the action of the direct product $S_m \times S_m$
of two symmetric groups, the first acting by left-multiplication
of permutation-matrices and the second acting by
right-multiplication of permutation-matrices.
Asymptotically, the correct answer should thus be
$2^{m^2}/(m!)^2$ since a random {0,1} matrix of
huge square-size is almost surely invertible and
has almost surely a trivial stabilizer under the
above action of $S_m\times S_m$.
To compute the generating function of the associated
integer sequences is another (and probably more difficult)
story.
Best whishes, Roland Bacher
More information about the SeqFan
mailing list