Links of minimum degree and exact covering numbers
Abstract
The covering number C(v,k,t) is the least number of k-subsets, called blocks, of a v-set such that every t-subset lies in one of them. We reduce the question whether a covering with L blocks exists to the classification of links. If every point of such a covering lies in at least r blocks and (r+1)v>kL, some point lies in exactly r blocks, and its link, the blocks through it with the point removed, is a $(v-1,k-1,t-1)$-covering with r blocks. It then suffices to list these links up to isomorphism, to prove the list complete, and to show that no link in the list extends to a covering with L blocks. Completeness is certified by one unsatisfiable formula that excludes the listed classes, so the program that lists the links need not be trusted. In general the last two steps are decided by propositional satisfiability (SAT) solving, with every formula written by two separately implemented encoders and every refutation checked by a formally verified proof checker. For links with four blocks and t=3 we give the classification by hand, under a condition on the parameters. As an application we determine twenty-five covering numbers with t∈{3,4,5} in which the published lower bound was one less than the size of a known covering, among them C(39,24,3)=9.
Related
- Results for distinct covering systems with a prime minimum modulus q ≥ 11
- On the difference between clique partition and clique covering numbers
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- P-adic Curved Kakeya Sets, Projection Theorem and Covering Numbers
- Positive Square Energy of Graphs with Minimum Degree at Least Two
BibTeX
@misc{requeijo2026links,
title = {{Links of minimum degree and exact covering numbers}},
author = {Alfonso Gippini Requeijo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31696},
eprint = {2610.31696},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31696},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Links of minimum degree and exact covering numbers
AU - Alfonso Gippini Requeijo
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.31696
UR - https://arxiv.org/abs/2610.31696
AB - The covering number C(v,k,t) is the least number of k-subsets, called blocks, of a v-set such that every t-subset lies in one of them. We reduce the question whether a covering with L blocks exists to the classification of links. If every point of such a covering lies in at least r blocks and (r+1)v>kL, some point lies in exactly r blocks, and its link, the blocks through it with the point removed, is a $(v-1,k-1,t-1)$-covering with r blocks. It then suffices to list these links up to isomorphism, to prove the list complete, and to show that no link in the list extends to a covering with L blocks. Completeness is certified by one unsatisfiable formula that excludes the listed classes, so the program that lists the links need not be trusted. In general the last two steps are decided by propositional satisfiability (SAT) solving, with every formula written by two separately implemented encoders and every refutation checked by a formally verified proof checker. For links with four blocks and t=3 we give the classification by hand, under a condition on the parameters. As an application we determine twenty-five covering numbers with t∈{3,4,5} in which the published lower bound was one less than the size of a known covering, among them C(39,24,3)=9.
ER -