Combinatorial covering designs

Combinatorial covering designs

Definitions and mathematical statement

Let $v,k,t$ be integers with $1\le t\le k\le v$, and let $V=\{1,\ldots,v\}$. A $(v,k,t)$ covering is a family $\mathcal B\subseteq\binom Vk$ of $k$-element subsets, called blocks, such that each $T\in\binom Vt$ is contained in at least one block. Repeated copies of a block provide no additional coverage and are omitted. The covering number is \[ C(v,k,t)=\min\left\{|\mathcal B|: \forall T\in\binom Vt\ \exists B\in\mathcal B\ (T\subseteq B)\right\}. \] Relabelling $V$ does not change this number. Coverage is by containment, not by intersection of a prescribed size, and a $t$-set may occur in several different blocks.

Determine $C(v,k,t)$, preferably through useful formulas, recurrences or sharp bounds across parameter families, and construct coverings attaining the claimed values. Counting incidences between blocks and $t$-sets gives the elementary benchmark \[ C(v,k,t)\ge \left\lceil\frac{\binom vt}{\binom kt}\right\rceil. \] If the unrounded ratio is attained, every $t$-set occurs in exactly one block; divisibility and structural restrictions can prevent this. The boundary cases include $C(v,k,k)=\binom vk$ and $C(v,v,t)=1$.

The request is a general extremal and constructive problem, rather than a single universal equality suggested by the counting bound. A finite exhaustive search defines an algorithm in principle; the intended advance is a mathematically useful exact determination or improved construction and lower-bound method.

Short English statement

What is the smallest family of $k$-subsets covering every $t$-subset of a $v$-element set, and how can optimal families be constructed?

Research attempt: point links, alteration, and exact test families

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. The prompt asks for a genuine attempt with an adversarial check, rather than a claimed solution. We work with distinct blocks and containment coverage. The original page [S2] cites Schönheim's point-link lower bound and construction work. The authors' paper [S3] develops constructions; Gordon's maintained repository [S4] distinguishes an exhibited covering from a proof of optimality. The arguments below recover elementary bounds and exact subfamilies, without claiming improvement over those sources.

1. A stronger lower bound from every point.

Let $b=|\mathcal B|$ and $b_x=|\{B\in\mathcal B:x\in B\}|$. For $t\ge2$, deleting $x$ from those blocks gives a $(v-1,k-1,t-1)$ covering: any $(t-1)$-set outside $x$ extends with $x$ to a target $t$-set. Consequently \[ kb=\sum_{x\in V}b_x\ge v C(v-1,k-1,t-1),\qquad C(v,k,t)\ge\left\lceil\frac vk C(v-1,k-1,t-1)\right\rceil. \] Iterating, with $C(v,k,1)=\lceil v/k\rceil$, gives nested ceilings. The last equality follows by the singleton incidence lower bound and partitioning the vertices into groups of size at most $k$, extending each group to a $k$-set. Integer rounding inside the recurrence can strictly strengthen rounding the final ratio only.

2. A quantified random construction with repair.

Write $N=\binom vt$ and $b_0=\binom kt$. A uniformly random $k$-set contains any fixed $t$-set with probability $b_0/N$. Select $m$ blocks independently with replacement. The expected number $U$ of uncovered targets is \[ \mathbb E U=N(1-b_0/N)^m\le N\exp(-mb_0/N). \] For each uncovered target choose any containing $k$-set and add it. Remove duplicates. The repaired family has size at most $m+U$, so some outcome proves \[ C(v,k,t)\le\left\lfloor m+N\exp(-mb_0/N)\right\rfloor. \] The floor is legitimate because the optimum is an integer bounded by the real expectation. For $b_0>1$, taking $m=\lceil (N/b_0)\log b_0\rceil$ gives an upper bound at most $(N/b_0)(1+\log b_0)+1$. This is an existence construction with a repair procedure, not a proof that a random sample is always good.

3. Two exact checks.

For $k=v-1$, every block is the complement of one omitted point. If the distinct omitted points form $D$, a target $T$ is uncovered exactly when $D\subseteq T$. Hence coverage holds exactly when $|D|>t$, and $C(v,v-1,t)=t+1$ for $1\le t\le v-1$. For $(v,k,t)=(7,3,2)$, use vertices $\mathbb Z/7\mathbb Z$ and the seven translates of $\{0,1,3\}$. The six ordered differences of this triple are $1,2,3,4,5,6$, each once. Therefore each ordered pair of distinct vertices occurs in one translated block, and every unordered pair is covered. The incidence lower bound is $21/3=7$, proving optimality.

Verification and first remaining gap.

The random calculation uses containment, not intersection. Its repair step is possible because $t\le k\le v$. The point-link argument requires $t\ge2$ and explicitly supplies its $t=1$ base. The two exact families match their lower bounds; a local enumeration checked the 21 pairs in the seven-block construction. Outside such families, neither the nested ceilings nor alteration proves equality: the former omits compatibility between links, while the latter pays for overlaps and repairs. Closing that gap uniformly would require additional structure.

Reproduction of finite checks.

The finite checks stated above were run with Python 3 using the repository script [C1]. They verify the stated examples and finite ranges only.

Final status

UNRESOLVED. Exact boundary families and a seven-point example are verified; the general determination and optimal construction problem is not solved. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3058 (OPG-762), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Combinatorial covering designs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/covering_designs.
• S3 D. M. Gordon, G. Kuperberg and O. Patashnik, New constructions for covering designs, author preprint, 1995. Checked 1 October 2026. https://arxiv.org/abs/math/9502238.
• S4 D. M. Gordon, Covering Designs, La Jolla Combinatorics Repository, maintained construction database. Checked 1 October 2026. https://dmgordon.org/covering-designs/.
• C1 Reproducible finite-check code, executed 1 October 2026 with Python 3 (standard library only): scripts/check_attempt_batch_geometry_2026_10_01.py.