Sharp bounds, stability, and arithmetic fluctuations for induced pentagons
Abstract
We prove that every graph with m>0 edges contains at most 3/2√2(m/5)5/2 induced pentagons. Equality holds precisely for balanced blow-ups of the Clebsch graph, together with isolated vertices. The bound and equality classification extend to arbitrary nonnegative vertex weights and to all graphons, including fractional graphons. Moreover, a deficit of ε in the normalized ratio can be repaired by O(√εm) edge edits on the original vertex set, producing an exactly balanced Clebsch blow-up and isolates. The exponent 1/2 is optimal. We further separate the linear cost of adjacency errors from the quadratic cost of class imbalance. This yields an arithmetic description of the finite-edge deficit and its explicit second-order term, with a uniform power-saving remainder. For each fixed integer j, the exact extremal count at m=40k2+j is eventually an integer coefficient polynomial in k, computable by a finite enumeration; we do not quantify its threshold of validity. The proof combines global variational conditions, an active-density bound, and an exact rational certificate on the $1,044$ graphs of order seven. A positive-slope identity permits a single rational reference density. An exact conditional span excludes triangles at equality, after which degree and codegree identities determine the Clebsch structure. All finite certificates admit independent verification using integer arithmetic.
Related
- Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings
- A Divisor-Weighted Golomb Sequence: Zeta Asymptotics and Arithmetic Fluctuations
- Upper bounds for arithmetic functions over polynomial values via Chebotarev--Sato--Tate distributions
- Square-root logarithmic bounds for the arithmetic complexity of factorial multiples
- A simple stability analysis of the Lanczos algorithm in finite precision arithmetic
BibTeX
@misc{xu2026sharp,
title = {{Sharp bounds, stability, and arithmetic fluctuations for induced pentagons}},
author = {Youwen Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40691},
eprint = {2610.40691},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40691},
}
RIS
TY - UNPB
TI - Sharp bounds, stability, and arithmetic fluctuations for induced pentagons
AU - Youwen Xu
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.40691
UR - https://arxiv.org/abs/2610.40691
AB - We prove that every graph with m>0 edges contains at most 3/2√2(m/5)^5/2 induced pentagons. Equality holds precisely for balanced blow-ups of the Clebsch graph, together with isolated vertices. The bound and equality classification extend to arbitrary nonnegative vertex weights and to all graphons, including fractional graphons. Moreover, a deficit of ε in the normalized ratio can be repaired by O(√εm) edge edits on the original vertex set, producing an exactly balanced Clebsch blow-up and isolates. The exponent 1/2 is optimal. We further separate the linear cost of adjacency errors from the quadratic cost of class imbalance. This yields an arithmetic description of the finite-edge deficit and its explicit second-order term, with a uniform power-saving remainder. For each fixed integer j, the exact extremal count at m=40k^2+j is eventually an integer coefficient polynomial in k, computable by a finite enumeration; we do not quantify its threshold of validity. The proof combines global variational conditions, an active-density bound, and an exact rational certificate on the $1,044$ graphs of order seven. A positive-slope identity permits a single rational reference density. An exact conditional span excludes triangles at equality, after which degree and codegree identities determine the Clebsch structure. All finite certificates admit independent verification using integer arithmetic.
ER -