Erdős Problem #627

Problem 627 (Round 2)

1) ROUND-2 OBJECTIVE

Path C: isolate the exact Ramsey-theoretic obstruction and convert the problem to an inverse-threshold statement on the $n/(\log n)^2$ scale.

Round 1 produced a self-contained probabilistic lower bound and a basic Ramsey-number lower bound, but it still did not identify the correct $\limsup$, nor did it isolate the exact place where the open difficulty remains. The most promising Round-2 move is therefore to combine the new 2026 Ramsey-theoretic information with a precise inverse-threshold theorem.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

• The probabilistic lower bound \[ f(n)\ge \left(\frac14+o(1)\right)\frac{n}{(\log_2 n)^2}. \]
• The Ramsey lower-bound mechanism: if $R(k,k)\le n < R(k+1,k+1)$, then \[ f(n)\ge \frac{n}{k^2}. \]

Throughout this section, $\log$ means $\log_2$.

3) NEW INSIGHT / TOOL (ROUND 2)

There are two genuinely new ingredients in this round.

1. A new exact theorem of Araujo--Filipe--Miyazaki gives the exact value of \[ \limsup_{n\to\infty}\frac{f(n)(\log n)^2}{n} \] in terms of a Ramsey envelope parameter $M$, and a lower bound on the corresponding $\liminf$ in terms of the diagonal Ramsey lower rate $L$.

2. I prove an inverse-threshold theorem for monotone functions on the $n/(\log n)^2$ scale. Applied to \[ Q(x):=\min\{n\in\mathbb N:f(n)\ge x\}, \] it converts limsup/liminf information about $f(n)(\log n)^2/n$ into exact liminf/limsup information about $Q(x)/(x(\log x)^2)$.

4) ATTACK PLAN (ROUND 2)

The exact gaps after Round 1 are:

• Round 1 did not identify $\limsup f(n)(\log n)^2/n$.
• Round 1 did not isolate the exact obstruction to the existence of the limit.
• Round 1 did not convert the problem to an equivalent inverse-threshold problem.

The plan is:

1. import the checked external theorem of Araujo--Filipe--Miyazaki;
2. prove an inverse theorem for $Q(x)$;
3. combine the two to obtain an exact obstruction statement: the limsup side is already completely understood, and the remaining open gap is the mismatch between the diagonal quantity $L$ and the off-diagonal envelope $M$.

5) WORK (ROUND 2)

Checked external theorem ([AFM25], Theorems 2.1 and 2.2).

Define \[ g(n):=\frac{f(n)(\log n)^2}{n}, \] \[ M:=\limsup_{t\to\infty}\max_{1\le s\le t}\frac{\log R(s,t)}{\sqrt{st}}, \qquad L:=\liminf_{k\to\infty}\frac{\log R(k,k)}{k}. \] Then \[ \limsup_{n\to\infty} g(n)=M^2, \qquad \liminf_{n\to\infty} g(n)\ge L^2. \] Moreover, [AFM25] proves the currently best asymptotic upper bound \[ f(n)\le (3.71943+o(1))\frac{n}{(\log n)^2}. \]

No extra hypotheses are needed for these statements.

Claim 627.1 (monotonicity and logarithmic location of the inverse threshold).

The function $f(n)$ is nondecreasing. If \[ Q(x):=\min\{n\in\mathbb N:f(n)\ge x\}, \] then $Q(x)$ is well-defined for all sufficiently large $x$, and \[ \frac{\log Q(x)}{\log x}\to 1 \qquad (x\to\infty). \]

Proof. Monotonicity follows by adding isolated vertices: if $G$ witnesses $f(n)$, then $G\cup I_1$ has the same values of $\chi$ and $\omega$, so $f(n+1)\ge f(n)$.

By Erdős' theorem, $f(n)=\Theta(n/(\log n)^2)$, so there exist $0<c<C$ and $n_0$ such that for all $n\ge n_0$, \[ c\frac{n}{(\log n)^2}\le f(n)\le C\frac{n}{(\log n)^2}. \] Let $n:=Q(x)$. Then $x\le f(n)\le Cn/(\log n)^2$, hence \[ \log x\le \log n + O(1). \] Also $x>f(n-1)\ge c(n-1)/(\log(n-1))^2$ for large $x$, so \[ \log x\ge \log(n-1)-2\log\log(n-1)+O(1). \] Thus \[ \log n-\log x=O(\log\log n), \] and dividing by $\log x\sim \log n$ gives \[ \frac{\log Q(x)}{\log x}\to 1. \] $\square$

Claim 627.2 (inverse theorem on the $n/(\log n)^2$ scale).

Let \[ \gamma_-:=\liminf_{n\to\infty}\frac{f(n)(\log n)^2}{n}, \qquad \gamma_+:=\limsup_{n\to\infty}\frac{f(n)(\log n)^2}{n}. \] Then \[ \liminf_{x\to\infty}\frac{Q(x)}{x(\log x)^2}=\frac{1}{\gamma_+}, \qquad \limsup_{x\to\infty}\frac{Q(x)}{x(\log x)^2}=\frac{1}{\gamma_-}. \]

Proof. We first prove the formula for the liminf.

Fix $\varepsilon>0$. By the definition of $\gamma_+$, for all large $n$, \[ f(n)\le (\gamma_++\varepsilon)\frac{n}{(\log n)^2}. \] Let $n:=Q(x)$. Then $x\le f(n)$, so \[ x\le (\gamma_++\varepsilon)\frac{n}{(\log n)^2}, \] that is, \[ \frac{Q(x)}{x(\log x)^2} = \frac{n}{x(\log x)^2} \ge \frac{1}{\gamma_++\varepsilon}\cdot \frac{(\log n)^2}{(\log x)^2}. \] By Claim 627.1, $\log n/\log x\to 1$. Hence \[ \liminf_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\ge \frac{1}{\gamma_++\varepsilon}. \] Letting $\varepsilon\downarrow 0$ gives \[ \liminf_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\ge \frac{1}{\gamma_+}. \]

For the reverse inequality, choose a sequence $n_j\to\infty$ such that \[ \frac{f(n_j)(\log n_j)^2}{n_j}\to \gamma_+. \] Set $x_j:=f(n_j)$. Then $Q(x_j)\le n_j$, so \[ \frac{Q(x_j)}{x_j(\log x_j)^2} \le \frac{n_j}{f(n_j)(\log x_j)^2} = \frac{1}{\frac{f(n_j)(\log n_j)^2}{n_j}}\cdot \frac{(\log n_j)^2}{(\log x_j)^2}. \] Since $x_j=f(n_j)=\Theta(n_j/(\log n_j)^2)$, we have $\log x_j/\log n_j\to 1$. Therefore \[ \liminf_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\le \frac{1}{\gamma_+}. \] This proves the liminf identity.

Now prove the formula for the limsup.

Fix $\varepsilon>0$. By the definition of $\gamma_-$, for all large $n$, \[ f(n)\ge (\gamma_--\varepsilon)\frac{n}{(\log n)^2}. \] Let $m:=Q(x)-1$. Then $f(m)<x$, so \[ x> (\gamma_--\varepsilon)\frac{m}{(\log m)^2}. \] Hence \[ \frac{Q(x)}{x(\log x)^2} = \frac{m+1}{x(\log x)^2} < \frac{m+1}{(\gamma_--\varepsilon)m}\cdot \frac{(\log m)^2}{(\log x)^2}. \] Since $x>f(m)$ and $x\le f(m+1)$, while $f(n)=\Theta(n/(\log n)^2)$, we also have $\log m/\log x\to 1$. Hence \[ \limsup_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\le \frac{1}{\gamma_--\varepsilon}. \] Let $\varepsilon\downarrow 0$ to get \[ \limsup_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\le \frac{1}{\gamma_-}. \]

For the reverse inequality, choose $m_j\to\infty$ such that \[ \frac{f(m_j)(\log m_j)^2}{m_j}\to \gamma_-. \] Set \[ x_j:=f(m_j)+\frac{1}{j}. \] Then $x_j>f(m_j)$, so $Q(x_j)\ge m_j+1$. Also $x_j/f(m_j)\to 1$, and $f(m_j)=\Theta(m_j/(\log m_j)^2)$, so $\log x_j/\log m_j\to 1$. Therefore \[ \frac{Q(x_j)}{x_j(\log x_j)^2} \ge \frac{m_j+1}{x_j(\log x_j)^2} \to \frac{1}{\gamma_-}. \] Thus \[ \limsup_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\ge \frac{1}{\gamma_-}. \] This proves the second identity. $\square$

Corollary 627.3 (exact inverse reformulation of Problem 627).

The limit \[ \lim_{n\to\infty}\frac{f(n)}{n/(\log n)^2} \] exists if and only if the limit \[ \lim_{x\to\infty}\frac{Q(x)}{x(\log x)^2} \] exists, and in that case the two limits are reciprocal.

Proof. This is immediate from Claim 627.2. $\square$

Corollary 627.4 (the exact Ramsey-theoretic obstruction).

With $Q(x)$, $L$, and $M$ as above, \[ \liminf_{x\to\infty}\frac{Q(x)}{x(\log x)^2}=\frac{1}{M^2}, \qquad \limsup_{x\to\infty}\frac{Q(x)}{x(\log x)^2}\le \frac{1}{L^2}. \]

Proof. By the checked theorem of Araujo--Filipe--Miyazaki, \[ \gamma_+=M^2,\qquad \gamma_-\ge L^2. \] Apply Claim 627.2: \[ \liminf \frac{Q(x)}{x(\log x)^2}=\frac{1}{\gamma_+}=\frac{1}{M^2}, \] and \[ \limsup \frac{Q(x)}{x(\log x)^2}=\frac{1}{\gamma_-}\le \frac{1}{L^2}. \] $\square$

Corollary 627.5 (a clean sufficient condition for the original limit).

If $L=M$, i.e. if \[ \liminf_{k\to\infty}\frac{\log R(k,k)}{k} = \limsup_{t\to\infty}\max_{1\le s\le t}\frac{\log R(s,t)}{\sqrt{st}}, \] then \[ \lim_{n\to\infty}\frac{f(n)}{n/(\log n)^2} \] exists and equals $L^2=M^2$.

Proof. The checked theorem gives \[ \liminf g(n)\ge L^2,\qquad \limsup g(n)=M^2. \] If $L=M$, then \[ M^2\le \liminf g(n)\le \limsup g(n)=M^2, \] so $g(n)\to M^2$. $\square$

Corollary 627.6 (updated interval for any putative limit).

If the limit \[ \lim_{n\to\infty}\frac{f(n)}{n/(\log n)^2} \] exists, then it lies in the interval $[1/4,\,3.71943]$.

Proof. The lower bound $1/4$ is exactly the Round-1 probabilistic bound. The upper bound $3.71943$ is the checked asymptotic upper bound from [AFM25]. $\square$

6) ADVERSARIAL VERIFICATION

I checked the new material against the main hidden pitfalls.

• Plateaux of $f(n)$. Because $f(n)$ is only nondecreasing, not strictly increasing, the choice $x_j=f(m_j)+1/j$ in Claim 627.2 is essential. It guarantees $Q(x_j)\ge m_j+1$ even if $f$ stays constant for long intervals.

• Replacement of $\log Q(x)$ by $\log x$. This was justified separately in Claim 627.1 using only the known theorem $f(n)=\Theta(n/(\log n)^2)$.

• Use of external results. The Araujo--Filipe--Miyazaki theorem was stated exactly as checked; no extra hypothesis was inserted into Corollary 627.4. Only Corollary 627.5 adds the extra condition $L=M$, and it is explicitly isolated there.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advances over Round 1 are:

1. the limsup side of Problem 627 is now exact via the checked theorem \[ \limsup_{n\to\infty}\frac{f(n)(\log n)^2}{n}=M^2; \]
2. the problem has been converted exactly into an inverse-threshold statement for $Q(x)$;
3. the remaining obstruction is sharply isolated: the original limit would follow from the collapse of the diagonal lower Ramsey rate $L$ and the off-diagonal envelope $M$.

8) COMPLETION ESTIMATE

COMPLETION: 58%

9) REFERENCES

• [AFM25 ] I. Araujo, R. Filipe, and R. Miyazaki, A note on the maximum ratio between chromatic number and clique number, arXiv:2512.16062v2, 2026.
• [Bloom627 ] T. F. Bloom, Erdős Problem #627, accessed 2026-03-08.

OBJECTIVE AND SOURCE REVIEW

Erdős #627; independent attempt, 2026-09-23. Let $f(n)=\max_{|V(G)|=n}\chi(G)/\omega(G)$. Does $f(n)(\log_2 n)^2/n$ converge? I read all of 627.tex, including the inverse-threshold proof. Its sufficient condition $L=M$ is not a proved necessary condition; calling that equality the exact remaining obstruction overstates the deduction. I test whether elementary regularity of $f$ could close the gap.

WORK: BOUNDED INCREMENTS DO NOT FORCE A LIMIT

For $n\ge1$, \[ 0\le f(n+1)-f(n)\le1. \] The lower bound follows by adding an isolated vertex. For the upper bound, take an optimizing graph $G$ on $n+1$ vertices and delete any vertex, obtaining $H$. Then $\chi(G)\le\chi(H)+1$ and $\omega(G)\ge\omega(H)\ge1$, so $\chi(G)/\omega(G)\le f(n)+1$. Nevertheless these inequalities plus $f(n)=\Theta(n/(\log_2 n)^2)$ do not imply convergence. To see this, for fixed $a>b>0$ define for large real $x$ \[ h(x)=\frac{x}{(\log_2 x)^2}\left(a+b\sin(\log\log x)\right), \qquad F(n)=\lfloor h(n)\rfloor. \] Differentiation gives $h'(x)=(a+b\sin(\log\log x))/(\log_2 x)^2+O((\log x)^{-3})$. Thus eventually $0<h'(x)<1$, and $F$ is nondecreasing with increments zero or one. Yet \[ \liminf F(n)(\log_2n)^2/n=a-b,\qquad \limsup F(n)(\log_2n)^2/n=a+b. \] Integer rounding contributes only $o(1)$, and the phases of $\log\log n$ approach the maxima and minima along suitable integer subsequences.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The constructed $F$ is an abstract sequence, not the graph extremal function. It disproves only a proposed inference from monotonicity, bounded jumps and order of growth. The source's inverse transformation remains valid, but transfers rather than resolves oscillation. Its inequalities $\liminf g\ge L^2$ and $\limsup g=M^2$ allow convergence even when $L<M$; a stronger graph or Ramsey argument is still needed.

SOURCES CHECKED

Complete local source gpt_pro_5.4/627.tex; primary Araujo--Filipe--Miyazaki record https://arxiv.org/abs/2512.16062, checked 2026-09-23. No unverified numerical constant from that paper is needed above.

FINAL

UNRESOLVED. Elementary regularity is established and shown insufficient to force the desired limit.

COMPLETION ESTIMATE

Conservative subjective progress toward convergence. COMPLETION: 8%

Problem 627

1) FORMAL RESTATEMENT

Let $G$ range over all graphs on vertex set $[n]=\{1,\dots,n\}$. Let $\chi(G)$ denote the chromatic number and $\omega(G)$ the clique number. Define \[ f(n)\ :=\ \max\left\{ \frac{\chi(G)}{\omega(G)}:\ |V(G)|=n\right\}. \] (So $f(n)$ is the maximum possible ratio between chromatic number and clique number among $n$-vertex graphs.) We take $\log$ to be the natural logarithm unless explicitly written $\log_2$.

Question. Does the limit \[ \lim_{n\to\infty}\frac{f(n)}{n/(\log n)^2} \] exist (as a finite real number), 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 question as open. It records that Erdős proved \[ f(n)\asymp \frac{n}{(\log n)^2}, \] and that if the above limit exists, it must lie in $(\log 2)^2\cdot[1/4,1]$ (with $\log$ natural).

A very recent note (Araujo--Filipe, arXiv:2512.16062v1, Dec. 2025) connects the existence/value of the limit for $f(n)$ to the long-open problem of whether $\lim_{k\to\infty}\frac{\log R(k,k)}{k}$ exists for diagonal Ramsey numbers $R(k,k)$, under an additional conjecture (their Conjecture 1.1). The note also reports the first asymptotic improvement (since 1967) on the best known constant in an upper bound of the form $f(n)\le (C+o(1))\frac{n}{(\log n)^2}$ (with all logarithms base $2$ in that paper).

3) ATTACK PLAN

Since the question is a limit-existence problem and the best-known information ties $f(n)$ to Ramsey theory, my approach was:

1. Re-derive basic bounds with explicit constants. As a sanity check and as a baseline, prove (with full details) a lower bound $f(n)\ge c\,n/(\log n)^2$ with an explicit $c>0$ via the probabilistic method (random graphs).
2. Relate $f(n)$ to Ramsey numbers. Show how constructions of graphs with simultaneously small $\alpha(G)$ and $\omega(G)$ (Ramsey graphs) force lower bounds on $f(n)$, and how upper bounds on $f(n)$ would follow from uniform control of such Ramsey phenomena.
3. Assess whether the limit might fail to exist. Try to see whether known oscillations/unknowns in Ramsey asymptotics could plausibly imply oscillations of $f(n)(\log n)^2/n$. I did not find a rigorous oscillation construction.

4) WORK

I did not resolve the limit existence question. I provide a complete, self-contained proof of a classical Erdős-type lower bound with constant via random graphs, plus a precise Ramsey-based inequality that explains why the limit is entangled with diagonal Ramsey asymptotics.

4.1. A probabilistic lower bound: $f(n)\ge \frac{1}{4}\frac{n}{(\log_2 n)^2}$

4.2. A Ramsey-number lower bound (exact inequality)

Let $R(s,t)$ denote the Ramsey number, i.e. the least $N$ such that every graph on $N$ vertices has either a clique of size $s$ or an independent set of size $t$.

This proposition shows that fine asymptotics for $f(n)$ are controlled by the growth of $R(k,k)$.

4.3. Small-$n$ sanity check (exhaustive search for $n\le 6$)

I exhaustively enumerated all labeled graphs on $n\le 6$ vertices and computed $\chi(G)$ and $\omega(G)$ exactly. The maximum ratio $\chi/\omega$ is: \[ f(2)=f(3)=f(4)=1,\qquad f(5)=f(6)=\frac{3}{2}. \] A witness for $f(5)=3/2$ is the 5-cycle $C_5$ (which has $\chi=3$ and $\omega=2$); for $n=6$ a witness is $C_5$ plus an isolated vertex.

5) VERIFICATION

Theorem Theorem was checked line-by-line: it uses only union bounds, $\binom{n}{r}\le n^r$, and the standard inequality $\chi(G)\ge n/\alpha(G)$. Proposition Proposition follows directly from the definition of Ramsey numbers.

6) FINAL

UNRESOLVED.

1. The limit-existence problem for $f(n)/(n/(\log n)^2)$ remains open (per current literature summaries), and recent work connects it to deep open questions in Ramsey theory.
2. I provided a complete probabilistic lower bound with explicit constant $1/4$ (in base-$2$ logarithms), and a precise inequality linking $f(n)$ to diagonal Ramsey numbers.
3. These results do not determine whether $f(n)(\log n)^2/n$ converges; they do, however, explain why the constant is tied to the asymptotics of $R(k,k)$.
4. Any full resolution likely requires either (a) proving convergence of suitable Ramsey-number quotients or (b) producing an explicit oscillation phenomenon.

7) COMPLETION ESTIMATE

COMPLETION: 35%.