Set of all bipartite graphs

How do I create the set/list of all bipartite graphs?

Alternatively, how do I create the set/list of all 0-1 matrices of given size m*n?

Answer 1

[John D'Errico]

No problem. Well, there probably IS a problem, as people are far too often surprised at how big things get.

How do you generate the set of ALL possible binary matrices, of a given dimension? Think of it like this: EVERY such matrix can be represented by a single integer value. If you string out all m*n bits of that matrix into one number, then you should see you can represent any such matrix by one integer. For example, if you want to see the set of all 2x2 binary matrices, there are 16 possible such matrices.

M = reshape(dec2bin(0:2^4-1)',2,2,16)

M = 2×2×16 char array
M(:,:,1) =

    '00'
    '00'

M(:,:,2) =

    '00'
    '01'

M(:,:,3) =

    '01'
    '00'

M(:,:,4) =

    '01'
    '01'

M(:,:,5) =

    '00'
    '10'

M(:,:,6) =

    '00'
    '11'

M(:,:,7) =

    '01'
    '10'

M(:,:,8) =

    '01'
    '11'

M(:,:,9) =

    '10'
    '00'

M(:,:,10) =

    '10'
    '01'

M(:,:,11) =

    '11'
    '00'

M(:,:,12) =

    '11'
    '01'

M(:,:,13) =

    '10'
    '10'

M(:,:,14) =

    '10'
    '11'

M(:,:,15) =

    '11'
    '10'

M(:,:,16) =

    '11'
    '11'

I've left them in character form, as they will take up less space that way, and the display is a litte tighter that way.

But suppose you want to generate the set of all such 6x6 matrices? Easy to do for the 2x2 case, but for the 6x6 case, you will have

2^36

ans = 6.8719e+10

so roughly 70 billion matrices, each of size 6x6. Odds are you don't have the memory on your computer to store them all. Even if stored as one byte integers, so int8 or uint8, that would be around 2 terabytes of RAM.

The point is, your problem is trivial to solve, unless your problem is not completely trivial in size. So having taught you how to solve your problem, your next question will often be why do I keep running out of memory? Exponential growth is a nasty thing that often surprises people.

Anyway, the dec2bin thing will fail beyond a certain point too, since integers in MATLAB are limited to 52 bits as doubles, or 64 bits as uint64. But you would run out of RAM long before that point.

I would note that every time I see somone wanting to generate such a set of all possible matrices, it is often a brute force solution to a probem that is better solved using an optimization tool. But since we don't know why you want to generate this complete set, we can't give advice in the matter.