Large Maximal Intersecting Families with Covering Number Three
Abstract
Let n>2k and k≥4. The largest size of an intersecting family of k-subsets of [n] with covering number at least three is g1(n,k)=binomn−1k−1−3binomn−k−1k−1+binomn−k−2k−1+binomn−2kk−1+3, attained by a unique family up to isomorphism. We prove that every other maximal intersecting family ℱ with covering number three satisfies |ℱ|≤ M(n,k)=max{q(n,k),g2(n,k)}, where q(n,k)&=binomn−1k−1−3binomn−k−1k−1+binomn−k−3k−1+binomn−2k+1k−1+3, g2(n,k)&=g1(n,k)−binomn−k−3k−3+1. This bound is attained for every n>2k and k≥4, so M(n,k) is the second largest distinct size. For k=4, g1(n,4)=13n−69 and M(n,4)=12n−61. For k≥5, we have M(n,k)=q(n,k) when 2k<n≤3k−2 and M(n,k)=g2(n,k) when n≥3k−2; the two terms coincide only at n=3k−2. We also classify all families attaining M(n,k) that admit a critically shifted labeling, including additional nonisomorphic families at n=2k+1. The proof combines local replacements with an inverse-shift estimate and gives a new proof of the known maximum and its uniqueness.
Related
- Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige
- The maximum size of intersecting k-graphs with covering number k
- A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
- Domination and maximal intersecting families in comaximal graphs of commutative rings
- Structure of large t-intersecting families I: Stability for the Hilton--Milner--Frankl theorem
BibTeX
@misc{zhang2026large,
title = {{Large Maximal Intersecting Families with Covering Number Three}},
author = {Huajun Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00149},
eprint = {2611.00149},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00149},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Large Maximal Intersecting Families with Covering Number Three
AU - Huajun Zhang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00149
UR - https://arxiv.org/abs/2611.00149
AB - Let n>2k and k≥4. The largest size of an intersecting family of k-subsets of [n] with covering number at least three is g_1(n,k)=binomn−1k−1−3binomn−k−1k−1+binomn−k−2k−1+binomn−2kk−1+3, attained by a unique family up to isomorphism. We prove that every other maximal intersecting family ℱ with covering number three satisfies |ℱ|≤ M(n,k)=max{q(n,k),g_2(n,k)}, where q(n,k)&=binomn−1k−1−3binomn−k−1k−1+binomn−k−3k−1+binomn−2k+1k−1+3, g_2(n,k)&=g_1(n,k)−binomn−k−3k−3+1. This bound is attained for every n>2k and k≥4, so M(n,k) is the second largest distinct size. For k=4, g_1(n,4)=13n−69 and M(n,4)=12n−61. For k≥5, we have M(n,k)=q(n,k) when 2k<n≤3k−2 and M(n,k)=g_2(n,k) when n≥3k−2; the two terms coincide only at n=3k−2. We also classify all families attaining M(n,k) that admit a critically shifted labeling, including additional nonisomorphic families at n=2k+1. The proof combines local replacements with an inverse-shift estimate and gives a new proof of the known maximum and its uniqueness.
ER -