Difference Systems of Sets (DSS)

A difference system of sets (DSS) with parameters (n, τ₀, ..., τ_q-1,ρ) is a collection of q disjoint subsets Q_i of {1, 2, ..., n}, | Q_i| =τ_i, 0 ≤ i ≤ q-1, such that the multi-set

M ={ a-b ( mod n) | a in Q_i, b in Q_j, i≠j}

contains every number i, 1 ≤ i ≤ n-1 at least ρ times. A DSS is perfect if every number i is contained exactly ρ times in the multi-set of differences. A DSS is regular if all subsets Q_iare of the same size: τ₀ = τ₁ = ... = τ_q-1.

The following tables were computed by an algorithm developed by Hao Wang as a part of an NSF sponsored project on code synchronization.

Tables of DSS for q=2, 3, 4 :

Table 1: q = 2;

Table 2: q = 3;

Table 3: q = 4.

To download a C program that finds a DSS with given parameters n, q and ρ click here. The program searches for a DSS for every partition that meets the lower bound on r(n,q,ρ) if one exists.