Practical engineering combinatorial-design optimization problem

Question

I am a very experienced electrical engineer. I am kindly asking for help! There is a practical case in electrical engineering that leads to the following question.

Combinations without repetition (n=10, r=2) or C(10,2) Using Items: 1,2,3,4,5,6,7,8,9,0 List has 45 entries. https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html

Combination list C(10,2)

Basic engineering task is to make 45 separate measurements for each C(10,2)pair. Alternative is to make automated C(4,2) measurements in groups of four Items C(10,4) to cover again 45 pairs C(10,2).

The questions are: What is theoretically the minimal number of groups of four C(10,4) to cover all 45 combinations in C(10,2) ? What combinations C(10,4) are concrete solution ?

My concrete intuitive solution for C(10,4) is:

Combination list C(10,4)

So I came up with a solution of 10 combinations of C(10,4), which together cover 45 combinations of C(10,2).

Since each of the C(10,4) combinations gives 6 C(10,2) combinations, I have a total of 10x6 or 60 C(10,2) combinations, that is, 60-45=15 double C(10,2) combinations.

Theoretically, to get 45 C(10,2) combinations, 8 C(10,4) combinations should be enough, because 8x6=48 C(10,2) combinations, with only 3 duplicate C(10,2) combinations.

My mathematical knowledge is not enough to prove or disprove that claim.

My further effort was to write a VBA program to randomly calculate the most favorable combinations of C(10,4). After about 400,000 random calculations I got 4 solutions with 10 x C(10,4) given below:

Random Simulation Solution for Combination list C(10,4)

So, I got solutions that are not better than my intuitive solution, that is, they do not contain less than 10 combinations of C(10,4).

I would appreciate any help in terms of:

1. A concrete solution to the problem in the theoretically smallest possible number of C(10,4) combinations.
2. Theoretical proof for the smallest number of C(10,4) combinations.
3. Tip for a software tool that can help solve the problem.
4. Mathematical classification of the problem and reference to the relevant literature or a solution to a similar problem.

Thank you in advance!

Answer 1

According to the La Jolla Covering Repository, the best solution requires 9 quads.

Covering Designs

A (v,k,t)-covering design is a collection of k-element subsets, called blocks, of {1,2,…,v}, such that any t-element subset is contained in at least one block. This site contains a collection of good (v,k,t)-coverings. 

Here's a solution for a (10, 4, 2) design derived from their tables

[
  [0, 1, 2, 3],
  [0, 4, 5, 6],
  [0, 7, 8, 9],
  [1, 2, 4, 7],
  [1, 2, 5, 8],
  [1, 2, 6, 9],
  [3, 4, 5, 9],
  [3, 6, 7, 8],
  [4, 5, 7, 8],
]

Here's some Python code that verifies that these quads cover all 45 pairs, and lists the number of times each pair is covered.

Code

# Cover all pairs in a set of 10 items, using quads
from itertools import combinations
from collections import Counter

quads = [
  [0, 1, 2, 3],
  [0, 4, 5, 6],
  [0, 7, 8, 9],
  [1, 2, 4, 7],
  [1, 2, 5, 8],
  [1, 2, 6, 9],
  [3, 4, 5, 9],
  [3, 6, 7, 8],
  [4, 5, 7, 8],
]

# Count the pairs in each quad
pairs = Counter()
for row in quads:
    for pr in combinations(row, 2):
        pairs[pr] += 1

# List the pairs, from most common to least
print(len(pairs), "pairs")
for pr, cnt in pairs.most_common():
    print(pr, cnt)

Output

45 pairs
(1, 2) 4
(4, 5) 3
(7, 8) 3
(4, 7) 2
(5, 8) 2
(0, 1) 1
(0, 2) 1
(0, 3) 1
(1, 3) 1
(2, 3) 1
(0, 4) 1
(0, 5) 1
(0, 6) 1
(4, 6) 1
(5, 6) 1
(0, 7) 1
(0, 8) 1
(0, 9) 1
(7, 9) 1
(8, 9) 1
(1, 4) 1
(1, 7) 1
(2, 4) 1
(2, 7) 1
(1, 5) 1
(1, 8) 1
(2, 5) 1
(2, 8) 1
(1, 6) 1
(1, 9) 1
(2, 6) 1
(2, 9) 1
(6, 9) 1
(3, 4) 1
(3, 5) 1
(3, 9) 1
(4, 9) 1
(5, 9) 1
(3, 6) 1
(3, 7) 1
(3, 8) 1
(6, 7) 1
(6, 8) 1
(4, 8) 1
(5, 7) 1

Here's a live version of that code, running on the SageMathCell server.

Answer 2

$10$ "quads" (sets of size $4$) may be the best you can do.

There are $45$ "pairs" (subsets of size $2$). Each quad will contain $\binom 42 = 6$ of those $45$ pairs. So you need to have at least $8$ quads at a minimum.

You can have a maximum of $5$ quads that do not have any pairs in common between them: $$0123\quad0456\quad1478\quad2579\quad3689$$ However, each additional quad will necessarily repeat more than one pair already occurring, thus three additional quads will still not include $45$ pairs total. So the minimum number of quads should be at least $9$.

So far my attempts to find $9$ quads that work have been unsuccessful, but I don't have an argument that it is impossible (even my argument that $8$ quads is not reachable is not completely tight).