# Maximum dissociated sets of 0-1 vectors

Consider a set *S* of 0-1 vectors of *n* components.
We call *S* "dissociated" if no two distinct subsets of *S*
have the same sum. Note that the sum is over the integers and not
modulo 2.

Such sets of vectors are relevant in a number of problems, of
which we will mention one. Let K = |*S*|. Then
suppose we have a collection of *K* objects, each of which
has weight either *w*_{1} or *w*_{2},
where *w*_{1} are *w*_{2} are known.
Then by weighing *n* subsets of the objects, we can determine
the weights of all of the objects. The weighings can be chosen
in advance; if we can choose weighings on the basis of the results
of previous weighings, that's a different story. The reader is
invited to discover why all this is true.

An example of a dissociated set of 5-vectors is

{ (1,1,1,0,0),
(1,1,0,1,0),
(1,1,0,0,1),
(1,0,1,1,1),
(0,1,1,1,1),
(1,1,1,1,0),
(1,1,1,1,1) }

Let *K*(*n*) be the largest possible size of a set of
dissociated *n*-vectors. The exact value of *K*(*n*)
seems to be unknown in general, but asymptotically
*K*(*n*) ≈ ½ *n* log_{2} *n*.
On this page we give a complete catalogue of dissociated
sets of size *K*(*n*), for *n* ≤ 7.
Since permuting the columns doesn't change the property, we only
give one member of each equivalence class under that operation.

The files actually contain graphs in **graph6** format. See
the combinatorial data page about that. The graphs
are bipartite, with *n* vertices of the first colour (representing
the columns) and *K*(*n*) of the second colour (representing the rows).
An edge from the *i*th row to the *j*th column means that
the *i*th vector has "1" in its *j*th component.

## All largest dissociated sets

*n=2*: 2 sets of size 2

*n=3*: 2 sets of size 4

*n=4*: 48 sets of size 5

*n=5*: 877 sets of size 7

*n=6*: 114227 sets of size 9

*n=7*: 118485 sets of size 12

Page Master: Brendan McKay,
brendan.mckay@anu.edu.au

Up to the combinatorial data page