Skip to main content
MathOverflow

Return to Question

Fixed typos including those pointed out in the comment section. Removed the "group theory" tag.
Source Link
Yuichiro Fujiwara
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is to find the minimum amountnumber of subsets such a family can have.

I am interested in the case $(v,k,2)$. It seems to be equivalent to the problem of finding the minimum ammountnumber of copies of $K_k$ that are needed to cover the graph $K_v$.

When $k=3$ this problem may be solved optimally with a Steiner triple system if it exists, which happens if and only if $v$ is $0$$1$ or $3 \bmod 6$, in this case $\frac{(n(n-1)}{2}$$\frac{v(v-1)}{6}$ subsets are required.

My questions are the following:

  • Is the minimum of subsets for $(v,3,2)$ known when the congruence does not hold?
  • If not what are good bounds?
  • Does the problem with $t=2$ have another name (It seems like it may be more common than the general covering design)
  • Is the minimum amountnumber of subsets for $(v,k,2)$ known?
  • If not, which are some good bounds (specific values of $k$ are also welcome)

Thank you very much in advance Regards.

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is to find the minimum amount of subsets such a family can have.

I am interested in the case $(v,k,2)$. It seems to be equivalent to the problem of finding the minimum ammount of copies of $K_k$ that are needed to cover the graph $K_v$.

When $k=3$ this problem may be solved optimally with a Steiner triple system if it exists, which happens if and only if $v$ is $0$ or $3 \bmod 6$, in this case $\frac{(n(n-1)}{2}$ subsets are required.

My questions are the following:

  • Is the minimum of subsets for $(v,3,2)$ known when the congruence does not hold?
  • If not what are good bounds?
  • Does the problem with $t=2$ have another name (It seems like it may be more common than the general covering design)
  • Is the minimum amount of subsets for $(v,k,2)$ known?
  • If not, which are some good bounds (specific values of $k$ are also welcome)

Thank you very much in advance Regards.

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is to find the minimum number of subsets such a family can have.

I am interested in the case $(v,k,2)$. It seems to be equivalent to the problem of finding the minimum number of copies of $K_k$ that are needed to cover the graph $K_v$.

When $k=3$ this problem may be solved optimally with a Steiner triple system if it exists, which happens if and only if $v$ is $1$ or $3 \bmod 6$, in this case $\frac{v(v-1)}{6}$ subsets are required.

My questions are the following:

  • Is the minimum of subsets for $(v,3,2)$ known when the congruence does not hold?
  • If not what are good bounds?
  • Does the problem with $t=2$ have another name (It seems like it may be more common than the general covering design)
  • Is the minimum number of subsets for $(v,k,2)$ known?
  • If not, which are some good bounds (specific values of $k$ are also welcome)
Source Link
Gorka
Gorka
  • 1.8k
  • 2
  • 19
  • 31

covering designs of the form $(v,k,2)$

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is to find the minimum amount of subsets such a family can have.

I am interested in the case $(v,k,2)$. It seems to be equivalent to the problem of finding the minimum ammount of copies of $K_k$ that are needed to cover the graph $K_v$.

When $k=3$ this problem may be solved optimally with a Steiner triple system if it exists, which happens if and only if $v$ is $0$ or $3 \bmod 6$, in this case $\frac{(n(n-1)}{2}$ subsets are required.

My questions are the following:

  • Is the minimum of subsets for $(v,3,2)$ known when the congruence does not hold?
  • If not what are good bounds?
  • Does the problem with $t=2$ have another name (It seems like it may be more common than the general covering design)
  • Is the minimum amount of subsets for $(v,k,2)$ known?
  • If not, which are some good bounds (specific values of $k$ are also welcome)

Thank you very much in advance Regards.