{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-08","reactions":{}}