TheoremDB
All problems

[#P2562] Covering every five-set with eight-sets on sixteen points

Work on this problem in ChatGPT
A neutral matrix schematic for Covering every five-set with eight-sets on sixteen points.A code-rendered placeholder showing only the mathematical setup.
A neutral schematic of the objects and relations in the statement.

Problem. Let \(C(16,8,5)\) be the smallest size of a family \(\mathcal B\subseteq\binom{[16]}{8}\) such that every five-element subset of \([16]\) lies in some \(B\in\mathcal B\). Determine \(C(16,8,5)\).

1Remarks

Remark 1. This is the classical covering-design number with 16 points, block size 8, and covered-subset size 5.

Remark 2. Blocks are distinct; relabeling the 16 points preserves feasibility.

2What counts as a solution

  • Give a cover and a matching lower-bound certificate establishing the exact value.

1Status

Current status (The current table interval is 104 through 115). The live LJCR record gives 104 <= C(16,8,5) <= 115; the exact covering number remains unresolved.[2][3][4]

1Records

4 records

Notes and companion materialContext, examples, and computations

The published interval is 104 <= C(16,8,5) <= 115. A simple lexicographic greedy rule independently gives a verified 118-block cover, which provides a reproducible baseline for stronger searches.

Original intake status. The La Jolla Covering Repository currently records 104 <= C(16,8,5) <= 115; the exact value is unresolved there.

  • The repository entry at https://ljcr.dmgordon.org/cover/show_cover.php?k=8&t=5&v=16 supplies a 115-block cover and attributes the lower bound 104 to the Schonheim bound.
  • An exact solver could combine isomorph rejection, fractional-cover bounds, and branch certificates indexed by the first uncovered five-set.

Recorded example 1. The greedy baseline covers 56 new five-sets with each of its first 30 blocks and finishes after 118 blocks.

Computational notes

  • All 12870 eight-subsets and 4368 five-subsets were represented as exact bitsets. The lexicographic greedy rule selected 118 distinct blocks, and an independent union check verified coverage of all 4368 five-subsets. Each of the final eight choices covered 8 new five-subsets. The repository's displayed 115 blocks were also parsed as subsets of [16] and checked to cover every five-subset.
How the 4 records connectTyped relations and evidence flow
How the records connect to the problem

ProblemCovering every five-set with eight-sets on sixteen points

2See also

How to cite

TheoremDB contributors, “Covering every five-set with eight-sets on sixteen points,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/covering-design-16-8-5

This problem includes 4 records joined by 4 typed links, sourced from ljcr.dmgordon.org[2], current as of July 24, 2026.

1References

  1. Daniel M. Gordon, La Jolla Covering Repository, C(13,5,2) record (checked 26 July 2026). C(13,5,2) record: exact value 10 and lower-bound attribution. website · reference source · web version checked 2026-08-01 · checked 2026-07-24Source use: citation only.Records C(13,5,2)=10, the seed value used in the recursive lower-bound calculation.
  2. Packet source. Daniel M. Gordon, La Jolla Covering Repository, C(16,8,5) record and 115-block covering credited to Alessandro Jurcovich (checked 26 July 2026). C(16,8,5) bounds and the complete 115-block family credited to Alessandro Jurcovich. dataset · dataset source · dataset snapshot checked 2026-08-01 · checked 2026-07-24Source use: citation only.Supplies Jurcovich's 115 blocks and records the current interval 104 through 115 for C(16,8,5).Also cited at Live C(16,8,5) bound and 115-block family.Also cited at Complete 115-block list credited to Alessandro Jurcovich; independently replayed in cd1685-artifact-exhaustive-cover.Also cited at Inline CPython standard-library replay of the complete LJCR block list, executed 2026-07-24.Source named by the research packet.
  3. Johanan Schönheim, On Coverings, Pacific Journal of Mathematics 14(4) (1964), 1405-1411. The recursive covering inequality on pp. 1405-1407. journal article · primary source · version of record · checked 2026-07-24Source use: citation only.Provides the recursive covering inequality used to derive the lower bound 104.
  4. Daniel Gordon, Greg Kuperberg, and Oren Patashnik, New constructions for covering designs, arXiv:math/9502238v1 (1995). Daniel Gordon, Greg Kuperberg, and Oren Patashnik, New constructions for covering designs, Journal of Combinatorial Designs 3(4) (1995), 269-284; definition and small-parameter tables. preprint · reference source · arXiv:math/9502238v1 · checked 2026-07-24Source use: citation only.Gives the standard covering-design framework and small-parameter construction context used in the status audit.

Finite covering-design optimization with published bounds and an independently checked deterministic construction.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.