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 w1 or w2, where w1 are w2 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 log2 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 ith row to the jth column means that the ith vector has "1" in its jth component.
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
Page Master: Brendan McKay, brendan.mckay@anu.edu.au