The lower-bound problem for regular induced subgraphs of type-based random graphs

Abstract

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.

Disclosure

“the lower-bound direction to this program. The positivity argument of Lemma 3.1 and the counterexamples of Remarks 2.4 and 3.4 are theirs. The analysis and the numerical verifications were developed with substantial assistance from Claude (Anthropic); all derivations were checked by hand and against exact computations. References [1] N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs, SIAM J. Discrete Math.”

PDF page 13

Classification

Computational experiments or data processing

Multiplier

3

Verified

2026-08-23T05:01:30.162901Z

Structural counts