GPT 6 Astra Ultra attempt on Math-876
mathematicsErdős problemscontributionManuscript
Contents
Problem 620: the asymptotic order is determined in a July 2026 preprint
1) OBJECTIVE AND SOURCE REVIEW
Status review dated 2026-09-23. I read the complete supplied620.tex, whose target is the asymptotic order of the largest triangle-free induced subgraph guaranteed in every $n$-vertex $K_4$-free graph. Write this extremal function as $f_{3,4}(n)$. The supplied March 2026 account's remaining logarithmic gap has since been closed in a primary preprint. The result is attributed to its authors; it is not a new proof by this attempt. 2) WORK: MATCHING THE LITERATURE TO THE TARGET
Morris, Sahasrabudhe and Verstraëte, On the Erdős--Rogers function, arXiv:2607.16118v1, submitted 2026-07-17, state in Theorem 1.1 that for every fixed $s\ge2$, \[ f_{s,s+1}(n)=\Theta(\sqrt{n\log n}). \] Their Theorem 3.1 quantifies the upper bound for every sufficiently large $n$, not only a subsequence: there is an absolute $C$ such that for $n\ge s^C$ an $n$-vertex $K_{s+1}$-free graph exists whose every vertex set of size at least $Cs^3\sqrt{n\log n}$ contains a $K_s$. Substituting $s=3$ gives $f_{3,4}(n)=O(\sqrt{n\log n})$.The lower-bound reduction can be checked directly. Joret, Micek, Reed and Smid's published clique-colouring theorem, Corollary 2, gives a vertex colouring of any $n$-vertex graph with at most $C_0\sqrt{n/\log n}$ colours such that no inclusion-wise maximal clique of size at least two is monochromatic. In a $K_4$-free graph every triangle is such a maximal clique: an additional vertex extending it would create a $K_4$. Therefore each colour class induces a triangle-free graph. By the pigeonhole principle the largest class has at least \[ \frac{n}{C_0\sqrt{n/\log n}}=C_0^{-1}\sqrt{n\log n} \] vertices. Combining the two named results gives \[ \boxed{f_{3,4}(n)=\Theta(\sqrt{n\log n})}. \]
3) ADVERSARIAL VERIFICATION
The definitions match induced triangle-free vertex sets, rather than merely deleting edges to obtain a triangle-free spanning subgraph. The upper-bound theorem's quantifier covers all sufficiently large orders. The clique-colouring implication above is verified here, but the long probabilistic construction proving the new upper bound has not been independently reproved or formally checked in this attempt. The result determines the asymptotic order up to constants; it does not determine exact finite values or a sharp leading constant. The repository's official status snapshot may lag this newer literature and is a separate record.4) FINAL
RESOLVED IN CITED LITERATURE FOR THE ASYMPTOTIC-ORDER TARGET. The previous gap is closed by the stated July 2026 preprint theorem together with the clique-colouring result. This is an attributed literature resolution, not an original solution, and its upper bound relies on that named preprint.5) SOURCES CHECKED
The complete supplied version; R. Morris, J. Sahasrabudhe and J. Verstraëte, Theorems 1.1 and 3.1,https://arxiv.org/html/2607.16118v1; G. Joret, P. Micek, B. Reed and M. Smid, Tight Bounds on the Clique Chromatic Number, Corollary 2, https://arxiv.org/html/2006.11353v2, published in Electronic Journal of Combinatorics 28$3$ $2021$, P3.51. Primary statements and the reduction were checked 2026-09-23.