La Jolla Covering tables, how to use them? Are they optimized?

Question

Recently I asked this question about guaranteeing matching a certain number of lottery numbers, and the answer gave the right direction to what I'm looking for, La Jolla Covering tables.

But now that I've been studying the tables and trying to understand them, I'm not sure if I'm getting it at all.

As I mention in my post, I play lotto, where I pick 8 numbers and make 5 combinations of 5 each, like this:

1,2,3,4,5

1,2,3,4,6

1,2,3,5,6

1,2,3,7,8

4,5,6,7,8

This gives me the certainty that if the 5 winning lotto numbers are contained in my 8 numbers, I will hit at least 4 in 1 of my 5 tickets.

From what I've read in La Jolla Covering Repository:

A $(v,k,t)-$covering design is a collection of $k$-element subsets, called blocks, of $\{1,2,\ldots ,v\}$, such that any $t$-element subset is contained in at least one block.

From this, I think my design should be $(v=8,k=5,t=4)$, if I'm understanding correctly. If I go and check the table at the La Jolla repository, I get a table with 20 rows, which leads me to believe that I'm not understanding this at all.

What is it that I'm not understanding correctly? Can you elaborate your answer please?

Answer 1

I think this is the issue:

An $(8, 5, 4)$ covering design is a set $\mathcal{B}$ of subsets of $\{1, 2, \ldots, 8\}$ (hereafter I'll use $[8]$ to refer to $\{1,2, \ldots, 8\}$) such that any $4$-element subset of $[8]$ is a subset of some $B \in \mathcal{B}$.

What you have is not an $(8, 5, 4)$ design: for example, $\{1, 2, 4, 7\}$ isn't a subset of any of your five $5$-element subsets of $[8]$.

But, your sets are enough to guarantee (and I had Sage help me make sure!) that for all $5$-element subsets of $[8]$, at least one of its $4$-element subsets is a subset of one of your sets.

This is not my area of expertise, so I'm not aware of any good references for the sort of things you're looking to construct. But, they are not $(v, k, t)$ covering designs.

From the answer to your other question:

A Covering Design $C(v,k,t,m,l,b)$ is a pair $(V,B)$, where $V$is a set of $v$ elements (called points) and $B$ is a collection of $b$ $k$-subsets of $V$ (called blocks), such that every $m$-subset of $V$ intersects at least $l$ members of $B$ in at least $t$ points. It is required that $v \geq k \geq t$ and $m \geq t.$

You want $l=1,k=5,$ $V=\{1,2,\ldots,14\} \quad(v=14)$ etc. Google the "La Jolla Covering Repository" for extensive tables.

We can reconcile this with the definition given by La Jolla:

A $(v,k,t)-$covering design is a collection of $k$-element subsets, called blocks, of $\{1,2,\ldots ,v\}$, such that any $t$-element subset is contained in at least one block.

If we are talking about a $(v, k, t)$ covering design, it fits into the above definition, but it's suppressed some parameters: Namely, requiring every $t$-element subset to be contained in at least one block, we're stipulating that $m = t$ (in your case, $4$).

Specifically, your sets are a $$C(v = 8,\, k = 5,\, t = 4,\, m = 5,\, l = 1,\, b = 5)$$ covering design. But what's listed in La Jolla is a $$C(v = 8,\, k = 5,\, t=4,\, m=4,\, l=1,\, b=20)$$

covering design. I suspect that you need $b \ge 20$ subsets to cover $m = t = 4$-element subsets of $[8]$ (hence the $20$ sets in the repository) while, evidently, covering $m = 4$-element subsets of all $t = 5$-element subets of $[8]$ requires fewer sets; at most $b = 5$, as your collection shows.