k-partite design

Is the following true? For every n1,k2, there is a set S[n]k of size |S|=n2 such that every two k-tuples in S have at most one common entry.

Does anyone know if this is true? Is there a reference?


Assuming that “at most common entry” means that any two tuples (x1,,xk) and (y1,,yk) match in at most one position, that is, there is at most one i such that xi=yi.

The claim is false for n=2 and any k4. We would need n2=4 tuples x,y,z,w. Then each of y and z must differ from x in at least k1 positions, which implies that y and z match in at least k22 positions.

(If the meaning was that any two tuples contain at most one common value, regardless of position, the claim would fail already with n=2, k=2, because there are only four different tuples (1,1),(1,2),(2,1),(2,2), and (1,2),(2,1) have two common values 1 and 2.)

Source : Link , Question Author : Lior Gishboliner , Answer Author : Jukka Kohonen

Leave a Comment