2
$\begingroup$

I would like to know the explicit formula for the number of labelled $n\times k$ bipartite graphs without cycles of length $4$.

Equivalently, the number of $n\times k\;$ $0/1$-matrices with the following condition:

Inner product of any two rows is at most $1$.

Motivation for this comes from Enumeration of 0/1-matrices avoiding some 2x2 matrices by Ju and Seo.

  • 0
    Can you do a simpler problem, say, the number of labelled $n\times n$ bipartite graphs with no cycle of length 4?2012-01-18

1 Answers 1