---

A proof claim submitted on 2026-08-24 to the site's proof-claim tab by Samuel Korsky, who declares the model GPT-5.6 Pro, with the proof in an external file linked from the submission. The tab does not label the claim full or partial. The site states that a listing on the tab is no guarantee of correctness and that nobody associated with the site has examined the proof. The linked file is not held, and the two comments under the submission are not recorded.

Submission note. Posted to erdosproblems.com as a proof claim by Samuel Korsky (account SamKorsky) on 24 August 2026, giving "GPT-5.6 Pro" as the AI used:

The linked paper shows that Erdős's conjecture of $\ll n^{1 + o(1)}$ remains true even for an induced $k$-regular subgraph, which answers (up to log factors) the question of Szemerédi about $F(n, k)$ discussed in the problem notes. The proof combines an induced high-girth extraction theorem of Du, Girao, Hunter, McCarty and Scott with a parameterized form of the matching-sunflower argument of Chakraborti, Janzer, Methuku and Montgomery. Notes: This problem highlighted what seems to be a strength of AI; in a literature review, GPT quickly located relevant papers that could be combined in a novel way, and after some guidance was able to complete the argument linked.

The claim. Writing $F(n,k)$ for the least number of edges that forces an induced $k$-regular subgraph in an $n$-vertex graph, the submission asserts $F(n,k)\le n^{1+o(1)}$ for every fixed $k\ge3$: the bound Erdős conjectured for $k$-regular subgraphs holds for induced ones as well. The submission presents this as answering, up to logarithmic factors, Szemerédi's question about $F(n,k)$ that the site's commentary mentions, and describes the proof as combining an induced high-girth extraction theorem of Du, Girão, Hunter, McCarty and Scott with a parameterized form of the matching--sunflower argument of Chakraborti, Janzer, Methuku and Montgomery.

Covers. The problem's yes-or-no part. The submission's statement is Szemerédi's induced variant, which the problem's commentary records and the problem does not ask; but an induced $k$-regular subgraph is a $k$-regular subgraph, so $f_k(n)\le F(n,k)$ and the claimed $F(n,k)\le n^{1+o(1)}$ implies $f_k(n)\le n^{1+o(1)}$, the answer yes to the problem's yes-or-no part. That part was settled by Pyber's 1985 bound and, more sharply, by Janzer and Sudakov, on whose accepted claim the standing rests, and the submission does not claim an asymptotic formula for either quantity. In the other direction, the graphs of Pyber, Rödl and Szemerédi have no induced $3$-regular subgraph either, so $F(n,k)\ge cn\log\log n$; the gap between that bound and $n^{1+o(1)}$ is not addressed by the submission.

Depends on. Chakraborti, Janzer, Methuku and Montgomery, whose matching--sunflower argument the proof adapts; the induced extraction theorem it combines with is not in the library.

Standing. Claimed: the submission is pending on the site's tab, the site's label for the problem rests on the earlier refereed papers and not on it, no review of it was found, and it is not refereed.