Erdős Problem #626: independent continuation
Date: 23 September 2026. Source versions read in full:
626.tex in
gpt_pro_5.4.
1) OBJECTIVE AND SOURCE AUDIT
The two questions concern existence of asymptotic exponents for extremal girth at fixed chromatic number and extremal chromatic number at fixed girth. The source correctly relates these to inverse threshold functions. Inverting limsup and liminf does not prove that they coincide.
2) A PRECISE SUFFICIENT COMPOSITION PROPERTY
Fix a chromatic requirement $k\ge4$, and let $N_k(m)$ be the least number of vertices in a graph of chromatic number at least $k$ and girth greater than $m$. Suppose, additionally, that there exists $C\ge1$ such that \[
N_k(a+b)\le C N_k(a)N_k(b)\qquad(a,b\ge1). \tag{1}
\] Then $u_m=\log(CN_k(m))$ is subadditive. To see its limiting behaviour directly, fix $q$ and write $m=tq+r$, $0\le r<q$. Repeated subadditivity gives $u_m\le t u_q+O_q(1)$, hence $\limsup u_m/m\le u_q/q$. Taking the infimum over $q$ gives existence of $\lim u_m/m$. The usual positive finite exponential bounds then allow the inverse-threshold argument in the source to yield a limit for the girth divided by $\log n$.
3) WHY EXISTING ENVELOPES ARE INSUFFICIENT
Consider the monotone integer function \[
N(m)=\left\lceil\exp(2^{\lceil\log_2m\rceil})\right\rceil.
\] It satisfies $e^m\le N(m)\le e^{2m}+1$, but $\log N(m)/m$ tends to $1$ along $m=2^j$ and to $2$ along $m=2^j+1$. Its inverse threshold likewise has two different asymptotic ratios to $\log n$. Thus monotonicity and matching exponential order cannot by themselves establish the desired limit.
4) FAILED CONSTRUCTION AND REMAINING GAP
A disjoint union of two graphs keeps the larger chromatic number but takes the smaller girth. It therefore supplies no inequality of form $1$, whose girth parameter is additive. Identifying vertices has the same obstruction. I have not found a graph operation establishing $1$, or an adequate approximate variant, for these extremal thresholds. The fixed-girth chromatic-exponent question also remains untouched by this conditional result.
7) FINAL
UNRESOLVED. This isolates a concrete missing composition theorem and gives a countermodel to a purely monotone inversion proof; it does not establish a new graph bound. Problem record:
https://www.erdosproblems.com/626.
8) COMPLETION ESTIMATE
COMPLETION: 5% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.