HEXAGONbeta

Asymptotically optimal degree for the double Hall property

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by John Tripodo ↗

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

The minimum maximum degree for the double Hall property is asymptotic to sqrt(2 n). Deterministic balanced regular bipartite constructions attain this leading constant with the property on both shores and degree at most sqrt(2 n)+O(n^(21/80)) for every sufficiently large n. The construction repairs homology semibiplanes, pads by matched duplication, and completes to regularity. The all-order error term invokes the published Baker-Harman-Pintz prime-interval theorem; the formal transfer keeps that input as an explicit hypothesis.

Provenance statement

OpenAI tools assisted mathematical exploration, proof engineering, coding, computational verification, literature research, and manuscript drafting. John Tripodo directed the research and is responsible for the mathematical statements, proofs, citations, code, and final text. AI systems are not authors. Internal AI-assisted review and independent computational implementations are distinct from external human peer review; no external human peer review is claimed. No fresh Lean compilation is claimed for this editorial revision. The formal transfer retains the short-prime-interval input as an explicit hypothesis. Manuscript version 1.0.1. Dedicated repository: https://github.com/jjtripodo-lgtm/double-hall-optimal-degree. Published Zenodo DOI: 10.5281/zenodo.23552249.

References

  1. R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proc. London Math. Soc. (3) 83 (2001), 532--562.
  2. J. Barát, A. Grzesik, A. Jung, Z. L. Nagy and D. Pálvölgyi, The double Hall property and cycle covers in bipartite graphs, Discrete Math. 347 (2024), 114079.
  3. G. Chen, M. Lavrov, Y. Ma, Y. Su and J. Vandenbussche, Bipartite graphs with the double Hall property, Frontiers in Combinatorics and Number Theory 1 (2026), 38--59, doi:10.3934/fcnt.2026005.DOI
  4. R. Li, The number of primes in short intervals and numerical calculations for Harman's sieve, arXiv:2308.04458v8 (2025), preprint.arXiv
  5. G. E. Moorhouse, On the construction of finite projective planes from homology semibiplanes, European J. Combin. 11 (1990), 589--600.
  6. S. Severini, On the digraph of a unitary matrix, SIAM J. Matrix Anal. Appl. 25 (2003), 295--300; arXiv:math/0205187 .arXiv
  7. S. Severini and F. Szöllősi, A further look into combinatorial orthogonality, Electron. J. Linear Algebra 17 (2008), 376--388.

Version history

  1. v1Submitted by John TripodoInitial depositCurrentOct 22, 2026