Metraipolis › archive › dc_22ca7aa8d627

The lower-bound problem for regular induced subgraphs of type-based random graphs — arXiv:2608.08169

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.08169
License (as archived)
CC0-1.0
Archived
2026-10-19T09:07:09.534Z
SHA-256 of the archived text
3919afb0cadf2caa2ebb15361397c896d19b6d6fd04aceedb6a3b16270f72e48
Stable URL of this page
https://metraipolis.com/documento/dc_22ca7aa8d627

How to cite

The lower-bound problem for regular induced subgraphs of type-based random graphs — arXiv:2608.08169 — arXiv (en), https://arxiv.org/abs/2608.08169 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_22ca7aa8d627 (Metraipolis archive dc_22ca7aa8d627, sha256 3919afb0cadf2caa2ebb15361397c896d19b6d6fd04aceedb6a3b16270f72e48)
BibTeX
@misc{dc22ca7aa8d627,
  title = {The lower-bound problem for regular induced subgraphs of type-based random graphs — arXiv:2608.08169},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.08169},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_22ca7aa8d627; sha256 3919afb0cadf2caa2ebb15361397c896d19b6d6fd04aceedb6a3b16270f72e48},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08169. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a graph G let F(G) denote the largest order of a regular induced subgraph of G, and let f(n) = min{F(G) : |V(G)| = n}. A problem of Erdos, Fajtlowicz and Staton asks whether f(n)/log n -> infinity. Dyson and McKay have recently proved f(n) <= (sqrt(2e)+o(1)) sqrt(n) via a type-based random model ( arXiv:2604.08215 ). This paper concerns the opposite direction within the type-based family. We conjecture that every model of the family satisfies F(G) >= (sqrt(2e)-o(1)) sqrt(n) asymptotically almost surely, so that sqrt(2e) is the optimal constant obtainable from the family, and we prove the corresponding statement at exponent level -- F(G) >= n^{1/2-eps} -- conditionally on two explicitly stated hypotheses: a local limit lower bound for inhomogeneous degree sequences, and a correlation estimate at sublinear overlaps. The complementary overlap range, including full overlap, requires no correlation hypothesis. We further record the exact-curvature first-moment computation that independently identifies sqrt(2e), including a uniform trace bound on its determinant correction, and certified exact computations at orders up to 48 consistent with the predicted crossover F ~ min(n^{2/3}, sqrt(n/L)). This version substantially revises v1; see the note in Section 1.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.PR).
Categorie arXiv: Combinatorics (math.CO) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2608.08169 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:04:32.198Z dalla pagina https://arxiv.org/catchup/math.PR/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).