Regular induced subgraphs in bounded independent-edge arrays

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.PR — Probability

Contributed by Arthur Freitas Ramos ↗, David Barros Hulak, Ruy J. G. B. de Queiroz

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

Let GG be a random graph whose edges are independent and whose edge probabilities lie in [ξ,1−ξ][\xi,1-\xi] for a fixed 0<ξ<1/20<\xi<1/2. With probability at least 1−n−11-n^{-1}, GG contains a regular induced subgraph on at least cξ(log⁡n)2c_\xi(\log n)^2 vertices. If all expected degrees are equal, each prescribed order kk up to a small multiple of n2/3n^{2/3} occurs with failure probability at most exp⁡(−cn/k3/2)\exp(-cn/k^{3/2}), for kk sufficiently large. The same probability estimate holds up to order n2/(d+3)n^{2/(d+3)} for a Lipschitz kernel in dimension dd, and up to order n4/(r+7)n^{4/(r+7)} for an array admitting a bounded symmetric completion of rank at most rr. A linear product array has largest regular induced order Θ(n)\Theta(\sqrt n) 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

Most of the results stated in the abstract have been checked and understood by a human. Codex assisted with the manuscript revision and proof review. The associated Lean formalization is linked separately.

Formalizations

Tools used

OpenAI
Codex
Lean
Lean

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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

Version history

  1. v1 · 19 pagesSubmitted by ArthurRevised after moderator-requested changesCurrentNov 19, 2026