Id: arxiv/2608.08169 Url: https://arxiv.org/abs/2608.08169 Tags: math.CO, math.PR Score: 0 Title: The lower-bound problem for regular induced subgraphs of type-based random graphs Domain: math.CO Source: arxiv Authors: Ariel Edgardo Levy Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-08 Page: https://delphi.science/r/arxiv/2608.08169 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) 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…