Regular induced subgraphs in bounded independent-edge arrays
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
Let be a random graph whose edges are independent and whose edge probabilities lie in for a fixed . With probability at least , contains a regular induced subgraph on at least vertices. If all expected degrees are equal, each prescribed order up to a small multiple of occurs with failure probability at most , for sufficiently large. The same probability estimate holds up to order for a Lipschitz kernel in dimension , and up to order for an array admitting a bounded symmetric completion of rank at most . A linear product array has largest regular induced order with high probability, attaining the scale for dimension one and rank one. The proof weights each candidate set by the reciprocal of its success probability and controls the dependence due to shared edges.
Provenance statement
Formalizations
Tools used
- OpenAI
- Codex
- Lean
- Lean
References
- N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs , SIAM Journal on Discrete Mathematics 22 (2008), 1325--1337. doi:10.1137/070704927 (https://doi.org/10.1137/070704927).DOI
- A. Barvinok and J. A. Hartigan, The number of graphs and a random graph with a given degree sequence , Random Structures & Algorithms 42 (2013), 301--348. doi:10.1002/rsa.20409 (https://doi.org/10.1002/rsa.20409). Preprint: arXiv:1003.0356v3 (https://arxiv.org/abs/1003.0356v3).arXivDOI
- S. Chatterjee, Fluctuations of eigenvalues and second order Poincaré inequalities , Probability Theory and Related Fields 143 (2009), 1--40. doi:10.1007/s00440-007-0118-6 (https://doi.org/10.1007/s00440-007-0118-6).DOI
- P. W. Dyson and B. D. McKay, Ramsey numbers for regular induced subgraphs , preprint (2026), arXiv:2604.08215v3 (https://arxiv.org/abs/2604.08215v3).arXiv
- M. Isaev and B. D. McKay, Complex martingales and asymptotic enumeration , Random Structures & Algorithms 52 (2018), 617--661. doi:10.1002/rsa.20754 (https://doi.org/10.1002/rsa.20754).DOI
- M. Krivelevich, B. Sudakov and N. Wormald, Regular induced subgraphs of a random graph , Random Structures & Algorithms 38 (2011), 235--250. doi:10.1002/rsa.20324 (https://doi.org/10.1002/rsa.20324).DOI
- A. E. Levy, The lower-bound problem for regular induced subgraphs of type-based random graphs , preprint (2026), arXiv:2608.08169v2 (https://arxiv.org/abs/2608.08169v2).arXiv
- A. F. Ramos, D. B. Hulak and R. J. G. B. de Queiroz, Pair-trace absorption certificates for regular induced subgraphs , preprint (2026), arXiv:2604.23882v1 (https://arxiv.org/abs/2604.23882v1).arXiv
- A. F. Ramos, D. B. Hulak and R. J. G. B. de Queiroz, Regular induced subgraphs in bounded independent-edge arrays , Palomar Registry, 19 November 2026, version 1. Registry entry (https://palomar-registry.org/entry?id=PALOMAR-2026-11-19-000016&version=1); Lean source at commit 251dd555 (https://github.com/Arthur742Ramos/Math-Formalization/tree/251dd555eb636ac0eddb2387b348bad7f5539894/combinatorics/bounded-independent-edge-regular-subgraphs); coverage map (https://github.com/Arthur742Ramos/Math-Formalization/blob/251dd555eb636ac0eddb2387b348bad7f5539894/combinatorics/bounded-independent-edge-regular-subgraphs/COVERAGE.md).link