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

1

It may be worth noting that there are unsolved problems not far away from thhis question. In particular, there is the question, how many edges can such a graph have? Some bounds are known, but in general they are not known to be optimal. See this link on the Zarankiewicz problem. This suggests (but doesn't prove) that there may be no explicit formula for your question, or at least that it may be very hard to find one.

Here is a paper that deals with the question of bounding the number of edges in such a graph.