[#P2562] Covering every five-set with eight-sets on sixteen points
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
1Records
Notes and companion material
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 connect
ProblemCovering every five-set with eight-sets on sixteen points
2See also
- Orders of ternary row-orthogonal matrices with a full rowdesign theory
- Components of the Pasch-switch graph on STS(15) classesdesign theory
- Hadamard matrix conjecturedesign theory
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-5This page as plain text: covering-design-16-8-5.md
This problem includes 4 records joined by 4 typed links, sourced from ljcr.dmgordon.org[2], current as of July 24, 2026.
1References
- 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.
- 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.
- 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.
- 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.