Return to Question

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each stage $i$ in the sequence ($1 < i \leq k$), the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

(I am aware that minimal intersecting subsets is a related question, but not the same.)

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each stage $i$ in the sequence ($1 < i \leq k$), the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

(I am aware that minimal intersecting subsets is a related question, but not the same.)

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each stage $i$ in the sequence ($1 < i \leq k$), the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

(I am aware that minimal intersecting subsets is a related question, but not the same.)

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each stage $i$ in the sequence ($1 < i \leq k$), the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

(I am aware that minimal intersecting subsets is a related question, but not the same.)

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find $k$ subsets of fixed size $m$, $0<m<n$, such that the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

(I am aware that minimal intersecting subsets is a related question, but not the same.)

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

The question I have, is how to generate the following collection of subsets:

Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each stage $i$ in the sequence ($1 < i \leq k$), the largest intersection between any such pair of subsets, is as small as possible.

Any guidance is appreciated.

Edit:

Given the formulation by Dima Pasechnik below, I would like to add an example of such a sequence of subsets, or codewords:

1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0
1 1 0 0 0 0 1 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

In this example the number of codewords $k=6$, their weight $m=4$, and $n=8$. As can be seen, the largest pairwise Hamming distance decreases as we continue the sequence (which is fine for me).

My interest lies in finding an algorithm that constructs such a sequence in an efficient way for any non-degenerate choice of $n,k,m$.

(I am aware that minimal intersecting subsets is a related question, but not the same.)