we-solve (beta)

Math-879-A2 · revision r1 · on Math-879

gpt pro 5.2 attempt on Math-879

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 626
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. 4.1. Basic monotonicity
  7. 4.2. Inverse function viewpoint for $g_k(n)$
  8. 4.3. Inverse function viewpoint for $h^{(m)}(n)$
  9. 4.4. Small-$n$ sanity checks (exhaustive search for $n\le 6$)
  10. 5) VERIFICATION
  11. 6) FINAL
  12. 7) COMPLETION ESTIMATE

Problem 626

1) FORMAL RESTATEMENT

Throughout, graphs are finite, simple, undirected. The girth $\operatorname{girth}(G)$ is the length of the shortest cycle in $G$, with $\operatorname{girth}(G)=\infty$ if $G$ is acyclic. The chromatic number is $\chi(G)$. We take $\log$ to be the natural logarithm.

Fix an integer $k\ge 4$. For each $n\in\mathbb{N}$ define \[ g_k(n)\ :=\ \max\left\{\, m\in\mathbb{N}\ :\ \exists\text{ graph }G\text{ with }|V(G)|=n,\ \chi(G)=k,\ \operatorname{girth}(G)>m\,\right\}. \] Equivalently, $g_k(n)=\max\{\operatorname{girth}(G)-1:\ |V(G)|=n,\ \chi(G)=k\}$, since $k\ge4$ forces $\operatorname{girth}(G)<\infty$.

Question A. Does the limit \[ \lim_{n\to\infty}\frac{g_k(n)}{\log n} \] exist (as a finite real number), and if so what is its value?

Fix an integer $m\ge 3$. For each $n\in\mathbb{N}$ define \[ h^{(m)}(n)\ :=\ \max\left\{\,\chi(G)\ :\ \exists\text{ graph }G\text{ with }|V(G)|=n,\ \operatorname{girth}(G)>m\,\right\}. \]

Question B. Does the limit \[ \lim_{n\to\infty}\frac{\log h^{(m)}(n)}{\log n} \] exist, and if so what is its value?

2) QUICK LITERATURE/CONTEXT CHECK

Web browsing available: YES. Computation available: YES.

The Erdős Problems site lists this problem as open, with the following known bounds (for fixed $k\ge4$ and all sufficiently large $n$): \[ \frac{1}{4\log k}\,\log n\ \le\ g_k(n)\ \le\ \frac{2}{\log(k-2)}\,\log n + 1, \] with the lower bound attributed to Kostochka and the upper bound to Erdős.

For $h^{(m)}(n)$, Erdős proved a general lower bound $\displaystyle \lim_{n\to\infty}\frac{\log h^{(m)}(n)}{\log n}\gg \frac{1}{m}$, and for odd $m$ an upper bound $\displaystyle \lim_{n\to\infty}\frac{\log h^{(m)}(n)}{\log n}\le \frac{2}{m+1}$, and conjectured this upper bound is sharp for odd $m$. For even $m$ Erdős suggested the limit should lie in $[2/(m+2),\,2/m]$ but could not prove this even for $m=4$.

3) ATTACK PLAN

I attempted the following "meta" approaches, aiming either to (i) force the limit to exist by a general regularity principle, or (ii) exhibit mechanisms that could make the limit fail to exist.
  1. Invert the extremal functions. Define the inverse threshold function $N_k(M):=\min\{n:\exists\,G\text{ on }n\text{ vertices with }\chi(G)=k\text{ and }\operatorname{girth}(G)>M\}$. If $\log N_k(M)$ grows linearly in $M$ with an asymptotic slope, then $g_k(n)$ is asymptotically that slope's reciprocal times $\log n$. This reduces existence of $\lim g_k(n)/\log n$ to existence of $\lim \log N_k(M)/M$.

    Similarly, define $N^{(m)}(t):=\min\{n:\exists\,G\text{ on }n\text{ vertices with }\operatorname{girth}(G)>m\text{ and }\chi(G)\ge t\}$. If $N^{(m)}(t)$ is regularly varying (power law), then $\log h^{(m)}(n)/\log n$ has a limit, and vice versa. So one can try to prove "regular variation" for these inverse functions.

  2. Try to prove submultiplicativity/supermultiplicativity for $N_k(M)$. If one could build from two graphs (with chromatic number $k$ and large girth) a new graph whose vertex count is roughly the product while girth adds, one would get a submultiplicativity statement $N_k(M_1+M_2)\ \le\ C\,N_k(M_1)N_k(M_2)$ for some constant $C$, and hence by Fekete's lemma a limit for $\log N_k(M)/M$. I do not know an operation that simultaneously preserves exact chromatic number $k$ and yields additive girth in such a clean way.
  3. Oscillation search. To show non-existence, one would want two infinite sequences $n_j,n'_j\to\infty$ such that $g_k(n_j)\sim c_1\log n_j$ but $g_k(n'_j)\sim c_2\log n'_j$ with $c_1\ne c_2$. Since $g_k(n)$ is a maximum over graphs, oscillation would have to come from the availability of much better constructions only at certain sizes $n$, in a way that cannot be "filled in" for intermediate $n$ (e.g. by adding isolated vertices). I did not find a rigorous mechanism producing two different constants.

4) WORK

No complete solution (existence or non-existence of the limits) was found. I record rigorous structural facts that reduce the limit question to an inverse-growth question, plus small-$n$ sanity checks.

4.1. Basic monotonicity

Lemma: For fixed $k\ge4$, the function $n\mapsto g_k(n)$ is nondecreasing. For fixed $m\ge3$, the function $n\mapsto h^{(m)}(n)$ is nondecreasing.
Proof: If $G$ is a witness for $g_k(n)$ (resp. $h^{(m)}(n)$), then adding isolated vertices increases $n$ without changing $\chi(G)$ or introducing cycles. Hence the extremal value cannot decrease when $n$ increases. ∎

4.2. Inverse function viewpoint for $g_k(n)$

Define \[ N_k(M)\ :=\ \min\left\{\,n\in\mathbb{N}\ :\ \exists\text{ graph }G\text{ on }n\text{ vertices with }\chi(G)=k,\ \operatorname{girth}(G)>M\,\right\}. \] Then by definition, \begin{equation}\label{wsref-0-65-71-3a-69-6e-76-2d-72-65-6c} g_k(n)\ =\ \max\{\,M\in\mathbb{N}: N_k(M)\le n\,\}. \end{equation}
Proposition: Assume the limit \[ L_k\ :=\ \lim_{M\to\infty}\frac{\log N_k(M)}{M} \] exists and satisfies $0<L_k<\infty$. Then the limit \[ \lim_{n\to\infty}\frac{g_k(n)}{\log n} \] exists and equals $1/L_k$.
Proof: Let $n\to\infty$, and set $M:=g_k(n)$. By (eq:inv-rel) we have \[ N_k(M)\ \le\ n\ <\ N_k(M+1). \] Taking logarithms, \[ \log N_k(M)\ \le\ \log n\ <\ \log N_k(M+1). \] Divide through by $M$ (for large $n$ one has $M\to\infty$ because $g_k(n)\gg\log n$ from known bounds, but even without that, one can restrict to $n$ for which $M\ge1$): \[ \frac{\log N_k(M)}{M}\ \le\ \frac{\log n}{M}\ <\ \frac{\log N_k(M+1)}{M}. \] By the assumed limit for $\log N_k(\cdot)/(\cdot)$, \[ \frac{\log N_k(M)}{M}\to L_k,\qquad \frac{\log N_k(M+1)}{M}=\frac{M+1}{M}\cdot\frac{\log N_k(M+1)}{M+1}\to 1\cdot L_k=L_k. \] Hence $\log n/M\to L_k$, i.e. $M/\log n\to 1/L_k$, proving the claim. ∎

4.3. Inverse function viewpoint for $h^{(m)}(n)$

Fix $m\ge3$ and define \[ N^{(m)}(t)\ :=\ \min\left\{\,n\in\mathbb{N}\ :\ \exists\text{ graph }G\text{ on }n\text{ vertices with }\operatorname{girth}(G)>m,\ \chi(G)\ge t\,\right\}. \] Then \[ h^{(m)}(n)\ =\ \max\{\,t\in\mathbb{N}: N^{(m)}(t)\le n\,\}. \]
Proposition: Assume the limit \[ A_m\ :=\ \lim_{t\to\infty}\frac{\log N^{(m)}(t)}{\log t} \] exists and satisfies $0<A_m<\infty$. Then the limit \[ \lim_{n\to\infty}\frac{\log h^{(m)}(n)}{\log n} \] exists and equals $1/A_m$.
Proof: Let $n\to\infty$ and set $t:=h^{(m)}(n)$. Then $N^{(m)}(t)\le n< N^{(m)}(t+1)$, so \[ \log N^{(m)}(t)\ \le\ \log n\ <\ \log N^{(m)}(t+1). \] Divide by $\log t$ (for $t\ge2$): \[ \frac{\log N^{(m)}(t)}{\log t}\ \le\ \frac{\log n}{\log t}\ <\ \frac{\log N^{(m)}(t+1)}{\log t}. \] By hypothesis, $\frac{\log N^{(m)}(t)}{\log t}\to A_m$. Also \[ \frac{\log N^{(m)}(t+1)}{\log t} =\frac{\log N^{(m)}(t+1)}{\log(t+1)}\cdot\frac{\log(t+1)}{\log t}\ \to\ A_m\cdot 1=A_m. \] Hence $\log n/\log t\to A_m$, i.e. $\log t/\log n\to 1/A_m$, proving the claim. ∎

4.4. Small-$n$ sanity checks (exhaustive search for $n\le 6$)

I exhaustively enumerated all labeled graphs on $n\le 6$ vertices and computed $\chi(G)$, $\omega(G)$, and $\operatorname{girth}(G)$ by brute force.
  • For $k=4$ one finds $g_4(4)=g_4(5)=g_4(6)=2$, i.e. every $4$-chromatic graph on at most $6$ vertices contains a triangle (so $\operatorname{girth}=3$).
  • For $m=3$ (triangle-free graphs), one finds $h^{(3)}(5)=h^{(3)}(6)=3$, witnessed by $C_5$ (and $C_5$ plus an isolated vertex).
These checks are consistent with the definitions and with the general phenomenon that forcing larger girth rapidly forces larger $n$ for fixed chromatic number.

5) VERIFICATION

Propositions Proposition and Proposition were checked carefully: they use only the extremal definitions plus monotonicity of the inverse thresholds and basic limit algebra. The exhaustive $n\le 6$ computations serve as a consistency check of the definitions (not as evidence for asymptotics).

6) FINAL

UNRESOLVED.
  1. The question asks for existence (and value) of two asymptotic limits. Current known bounds leave a constant-factor gap for $g_k(n)/\log n$ and an exponent gap for $\log h^{(m)}(n)/\log n$ (especially for even $m$).
  2. I proved that existence of $\lim g_k(n)/\log n$ would follow from existence of $\lim \log N_k(M)/M$ for the inverse threshold $N_k(M)$, and similarly for $h^{(m)}$ via $N^{(m)}(t)$.
  3. I did not find (a) a construction proving the limits exist, nor (b) a mechanism forcing non-existence by oscillation.
  4. Any full resolution likely requires either new "product" constructions/subadditivity for $N_k(M)$ or sharp matching upper/lower constructions for $h^{(m)}(n)$.

7) COMPLETION ESTIMATE

COMPLETION: 25%.