Skip to main content
MathOverflow

Return to Answer

fixed arxiv front-end link and gave full published reference
Source Link
David Roberts ♦
David Roberts ♦
  • 35.5k
  • 11
  • 124
  • 349

The more general problem, as Ben Green says, is to cover every $t$-tuple by subsets of size $k$ in a set of size $v$. (These are more standard variables.) This is called a covering design. (It's not the same as a $(v,k,t)-\lambda$-design, because in those each tuple is covered the same number of times, rather than at least once.) Although there is no theorem to this effect, finding covering designs looks like an open-ended problem that will never be completely solved, even though there are many good ideas and it can be solved in some cases. In this respect it is like the problem of finding sphere packings, error-correcting codes, graphs with various properties, etc. Non-rigorously the La Jolla covering repository shows you that it looks that way, because many of the competitive covering designs, even for $t=2$, were found by methods such as simulated annealing and even "private tools".

As Ben also mentions, if $k$ and $t$ are fixed, then Rodl showed that the covering density converges to 1 as $v \to \infty$. In this limit covering designs are equivalent to packing designs up to an $o(1)$ fraction of slop. Rodl's technique is the "Rodl nibble", in which small clusters of blocks are added incrementally. However, it was discovered (see [arXiv:math/9511224]Asymptotically optimal covering designs, J. Combin. Theory Ser. A 75 (1996), no. 2, 270–280) that you might as well let a Rodl nibble be just a single block. This simplifies Rodl's construction to the random greedy algorithm. There is also a non-rigorous model that correctly predicts the rate at which the random greedy algorithm converges to density 1. There has been a lot of interesting work to close the gap between rigorous bounds on the random greedy algorithm, and the non-rigorous model of the algorithm.

If $k$ grows along with $v$, then there is no known asymptotic $1+o(1)$ bound even for $t=2$. (Unless $k$ grows so slowly that the arguments for $k$ fixed still work.) The volume lower bound, just the fact that the covering density is at least 1, can be improved to the Schonheim bound. (If $k$ is fixed then the Schonheim bound is the same as the volume bound up to $1+o(1)$.) It's easy to believe that the Schonheim bound is close to the truth for a wide range of parameters, but no such thing is proven except for the smallest values of $k$. For instance, when $k=3$, the Schonheim bound is always sharp.

The more general problem, as Ben Green says, is to cover every $t$-tuple by subsets of size $k$ in a set of size $v$. (These are more standard variables.) This is called a covering design. (It's not the same as a $(v,k,t)-\lambda$-design, because in those each tuple is covered the same number of times, rather than at least once.) Although there is no theorem to this effect, finding covering designs looks like an open-ended problem that will never be completely solved, even though there are many good ideas and it can be solved in some cases. In this respect it is like the problem of finding sphere packings, error-correcting codes, graphs with various properties, etc. Non-rigorously the La Jolla covering repository shows you that it looks that way, because many of the competitive covering designs, even for $t=2$, were found by methods such as simulated annealing and even "private tools".

As Ben also mentions, if $k$ and $t$ are fixed, then Rodl showed that the covering density converges to 1 as $v \to \infty$. In this limit covering designs are equivalent to packing designs up to an $o(1)$ fraction of slop. Rodl's technique is the "Rodl nibble", in which small clusters of blocks are added incrementally. However, it was discovered (see [arXiv:math/9511224]) that you might as well let a Rodl nibble be just a single block. This simplifies Rodl's construction to the random greedy algorithm. There is also a non-rigorous model that correctly predicts the rate at which the random greedy algorithm converges to density 1. There has been a lot of interesting work to close the gap between rigorous bounds on the random greedy algorithm, and the non-rigorous model of the algorithm.

If $k$ grows along with $v$, then there is no known asymptotic $1+o(1)$ bound even for $t=2$. (Unless $k$ grows so slowly that the arguments for $k$ fixed still work.) The volume lower bound, just the fact that the covering density is at least 1, can be improved to the Schonheim bound. (If $k$ is fixed then the Schonheim bound is the same as the volume bound up to $1+o(1)$.) It's easy to believe that the Schonheim bound is close to the truth for a wide range of parameters, but no such thing is proven except for the smallest values of $k$. For instance, when $k=3$, the Schonheim bound is always sharp.

The more general problem, as Ben Green says, is to cover every $t$-tuple by subsets of size $k$ in a set of size $v$. (These are more standard variables.) This is called a covering design. (It's not the same as a $(v,k,t)-\lambda$-design, because in those each tuple is covered the same number of times, rather than at least once.) Although there is no theorem to this effect, finding covering designs looks like an open-ended problem that will never be completely solved, even though there are many good ideas and it can be solved in some cases. In this respect it is like the problem of finding sphere packings, error-correcting codes, graphs with various properties, etc. Non-rigorously the La Jolla covering repository shows you that it looks that way, because many of the competitive covering designs, even for $t=2$, were found by methods such as simulated annealing and even "private tools".

As Ben also mentions, if $k$ and $t$ are fixed, then Rodl showed that the covering density converges to 1 as $v \to \infty$. In this limit covering designs are equivalent to packing designs up to an $o(1)$ fraction of slop. Rodl's technique is the "Rodl nibble", in which small clusters of blocks are added incrementally. However, it was discovered (see Asymptotically optimal covering designs, J. Combin. Theory Ser. A 75 (1996), no. 2, 270–280) that you might as well let a Rodl nibble be just a single block. This simplifies Rodl's construction to the random greedy algorithm. There is also a non-rigorous model that correctly predicts the rate at which the random greedy algorithm converges to density 1. There has been a lot of interesting work to close the gap between rigorous bounds on the random greedy algorithm, and the non-rigorous model of the algorithm.

If $k$ grows along with $v$, then there is no known asymptotic $1+o(1)$ bound even for $t=2$. (Unless $k$ grows so slowly that the arguments for $k$ fixed still work.) The volume lower bound, just the fact that the covering density is at least 1, can be improved to the Schonheim bound. (If $k$ is fixed then the Schonheim bound is the same as the volume bound up to $1+o(1)$.) It's easy to believe that the Schonheim bound is close to the truth for a wide range of parameters, but no such thing is proven except for the smallest values of $k$. For instance, when $k=3$, the Schonheim bound is always sharp.

Source Link
Greg Kuperberg
Greg Kuperberg
  • 56.6k
  • 10
  • 203
  • 282

The more general problem, as Ben Green says, is to cover every $t$-tuple by subsets of size $k$ in a set of size $v$. (These are more standard variables.) This is called a covering design. (It's not the same as a $(v,k,t)-\lambda$-design, because in those each tuple is covered the same number of times, rather than at least once.) Although there is no theorem to this effect, finding covering designs looks like an open-ended problem that will never be completely solved, even though there are many good ideas and it can be solved in some cases. In this respect it is like the problem of finding sphere packings, error-correcting codes, graphs with various properties, etc. Non-rigorously the La Jolla covering repository shows you that it looks that way, because many of the competitive covering designs, even for $t=2$, were found by methods such as simulated annealing and even "private tools".

As Ben also mentions, if $k$ and $t$ are fixed, then Rodl showed that the covering density converges to 1 as $v \to \infty$. In this limit covering designs are equivalent to packing designs up to an $o(1)$ fraction of slop. Rodl's technique is the "Rodl nibble", in which small clusters of blocks are added incrementally. However, it was discovered (see [arXiv:math/9511224]) that you might as well let a Rodl nibble be just a single block. This simplifies Rodl's construction to the random greedy algorithm. There is also a non-rigorous model that correctly predicts the rate at which the random greedy algorithm converges to density 1. There has been a lot of interesting work to close the gap between rigorous bounds on the random greedy algorithm, and the non-rigorous model of the algorithm.

If $k$ grows along with $v$, then there is no known asymptotic $1+o(1)$ bound even for $t=2$. (Unless $k$ grows so slowly that the arguments for $k$ fixed still work.) The volume lower bound, just the fact that the covering density is at least 1, can be improved to the Schonheim bound. (If $k$ is fixed then the Schonheim bound is the same as the volume bound up to $1+o(1)$.) It's easy to believe that the Schonheim bound is close to the truth for a wide range of parameters, but no such thing is proven except for the smallest values of $k$. For instance, when $k=3$, the Schonheim bound is always sharp.