Erdős Problem #620

Problem 620 $\#620$

1) ROUND-2 OBJECTIVE

Path (C): the global problem remains open, but the Round-1 lower bound \[ f(n)\ge \lfloor \sqrt n\rfloor \] can be upgraded to the best currently known lower bound \[ f(n)\ge c\sqrt{\frac{n\log n}{\log\log n}} \] for some absolute constant $c>0$. This closes the exact Round-1 gap on the lower-bound side and reduces the remaining uncertainty to the polylogarithmic factor between this and the upper bound \[ f(n)\ll \sqrt n\,\log n. \]

2) Round-1 FOUNDATION USED

I use the two Round-1 ingredients:

1. if $v$ is a vertex of a $K_4$-free graph, then the neighborhood $N(v)$ induces a triangle-free graph;
2. the proof strategy should split according to the maximum degree $\Delta$.

Round 1 used a greedy independent-set bound in the low-degree case. I will strengthen only that low-degree step.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is Shearer's theorem on the independence number of sparse $K_r$-free graphs. Specialised to $r=4$, it says that for sufficiently large maximum degree $d$, every $K_4$-free graph on $n$ vertices with maximum degree at most $d$ has an independent set of size \[ \Omega\!\left(\frac{n\log d}{d\log\log d}\right). \]

Replacing the Round-1 greedy bound \[ \alpha(G)\ge \frac{n}{d+1} \] by Shearer's bound upgrades the low-degree case from order $\sqrt n$ to order \[ \sqrt{\frac{n\log n}{\log\log n}}. \]

4) ATTACK PLAN (ROUND-2)

Let $G$ be $K_4$-free on $n$ vertices, and let $\Delta$ be its maximum degree.

1. If $\Delta$ is large, then a high-degree neighborhood $N(v)$ is already a large induced triangle-free subgraph.
2. If $\Delta$ is not large, then Shearer's theorem gives a large independent set, which is itself an induced triangle-free subgraph.
3. Optimise the tradeoff at \[ d_\ast=\sqrt{\frac{n\log n}{\log\log n}}. \]

This is exactly the Round-1 degree-splitting strategy, but with a much stronger low-degree theorem.

5) WORK (ROUND-2)

External theorem used.

I use the following result of Shearer.

Shearer $1995$. There exists an absolute constant $c_0>0$ and an absolute threshold $D$ such that every $K_4$-free graph on $n$ vertices with maximum degree $d\ge D$ has an independent set of size at least \[ c_0\,\frac{n\log d}{d\log\log d}. \]

Theorem 5.1.

There exists an absolute constant $c>0$ such that every $K_4$-free graph $G$ on $n$ vertices contains an induced triangle-free subgraph on at least \[ c\sqrt{\frac{n\log n}{\log\log n}} \] vertices. Equivalently, \[ f(n)=\Omega\!\left(\sqrt{\frac{n\log n}{\log\log n}}\right). \]

Proof.

Let $G$ be a $K_4$-free graph on $n$ vertices, and let $\Delta$ be its maximum degree.

Set \[ d_\ast=\sqrt{\frac{n\log n}{\log\log n}}. \]

We consider three cases.

Case 1: $\Delta\ge d_\ast$. Choose a vertex $v$ of degree $\Delta$. Then $G[N(v)]$ is triangle-free by the Round-1 neighborhood observation, and \[ |N(v)|=\Delta\ge d_\ast. \] So $G$ contains an induced triangle-free subgraph on at least $d_\ast$ vertices.

Case 2: $D\le \Delta<d_\ast$. Apply Shearer's theorem with $d=\Delta$. Then $G$ has an independent set of size at least \[ c_0\,\frac{n\log \Delta}{\Delta\log\log \Delta}. \] An independent set is an induced triangle-free subgraph.

Now the function \[ \phi(x)=\frac{\log x}{x\log\log x} \] is decreasing for all sufficiently large $x$, in particular for $x\ge D$ after enlarging $D$ if necessary. Since $\Delta<d_\ast$, we get \[ \frac{\log \Delta}{\Delta\log\log \Delta} \ge \frac{\log d_\ast}{d_\ast\log\log d_\ast}. \] Hence \[ \alpha(G)\ge c_0\,\frac{n\log d_\ast}{d_\ast\log\log d_\ast}. \]

For all sufficiently large $n$, \[ \log d_\ast = \frac12\log n+\frac12\log\log n-\frac12\log\log\log n \ge \frac13\log n, \] and also \[ \log\log d_\ast\le 2\log\log n. \] Therefore \[ \alpha(G)\ge \frac{c_0}{6}\, \frac{n\log n}{d_\ast\log\log n}. \] Using the definition of $d_\ast$, \[ \frac{n\log n}{d_\ast\log\log n} = \sqrt{\frac{n\log n}{\log\log n}} = d_\ast. \] So in Case 2 we again obtain an induced triangle-free subgraph of size at least \[ \frac{c_0}{6}\sqrt{\frac{n\log n}{\log\log n}}. \]

Case 3: $\Delta<D$. Then the trivial greedy bound gives \[ \alpha(G)\ge \frac{n}{D+1}. \] For sufficiently large $n$ this is much larger than $\sqrt{n\log n/\log\log n}$, since \[ \frac{n}{D+1}\bigg/\sqrt{\frac{n\log n}{\log\log n}} = \frac{\sqrt n}{D+1}\sqrt{\frac{\log\log n}{\log n}} \to \infty. \] So Case 3 is also stronger than the target lower bound for all large $n$.

Combining the three cases, every sufficiently large $n$-vertex $K_4$-free graph contains an induced triangle-free subgraph of size at least \[ c\sqrt{\frac{n\log n}{\log\log n}} \] for some absolute constant $c>0$.

By decreasing $c$ if necessary, the same asymptotic lower bound may be stated for all $n\ge 2$. $\square$

Corollary 5.2.

Combining Theorem 5.1 with the current upper bound \[ f(n)\ll \sqrt n\,\log n, \] we recover the currently best asymptotic window \[ \sqrt{\frac{n\log n}{\log\log n}} \ll f(n)\ll \sqrt n\,\log n, \] and in particular \[ f(n)=n^{1/2+o(1)}. \]

6) ADVERSARIAL VERIFICATION

1. The neighborhood argument is exactly the Round-1 observation: if $N(v)$ contained a triangle, adding $v$ would create a $K_4$.
2. Shearer's theorem is only applied in the range $\Delta\ge D$, where its hypotheses hold.
3. The monotonicity of \[ \phi(x)=\frac{\log x}{x\log\log x} \] is needed only for large $x$, so enlarging $D$ is harmless.
4. The low-degree case $\Delta<D$ was treated separately, so there is no hidden gap when $\log\log \Delta$ is small.
5. The conclusion is asymptotic; finite-$n$ issues are absorbed by shrinking the constant $c$.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 1 established only the elementary bound \[ f(n)\ge \lfloor \sqrt n\rfloor. \] This round upgrades that to the best currently known lower bound \[ f(n)\gg \sqrt{\frac{n\log n}{\log\log n}}, \] using Shearer's theorem together with the same maximum-degree split.

So the remaining gap is now exactly the current polylogarithmic gap between \[ \sqrt{\frac{n\log n}{\log\log n}} \quad\text{and}\quad \sqrt n\,\log n. \]

8) COMPLETION ESTIMATE

COMPLETION: 68%

9) REFERENCES

• J. B. Shearer, On the Independence Number of Sparse Graphs, Random Structures & Algorithms 7 $1995$, 269--271.
• D. Mubayi and J. Verstraëte, On the order of the classical Erdős--Rogers functions, 2024 preprint / 2025 publication version checked.
• T. F. Bloom, Erdős Problem #620, accessed 2026-03-08.
• Round-1 notes from the previous iteration of this investigation (used only for the neighborhood observation and the maximum-degree splitting strategy listed in Section 2).

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 supplied 620.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.

6) COMPLETION ESTIMATE

The asymptotic-order question is covered by the attributed literature result; this is not a measure of independent proof verification or of exact-value determination. COMPLETION: 100%

Problem 620

FORMAL RESTATEMENT

For a graph $G=(V,E)$ and $W\subseteq V$, let $G[W]$ denote the induced subgraph. Define \[ f(n)\ :=\ \min\left\{\ \max\left\{|W|:\ W\subseteq V(G),\ \text{$G[W]$ is triangle-free}\right\}:\ |V(G)|=n,\ \text{$G$ is $K_4$-free}\ \right\}. \] Equivalently, $f(n)$ is the largest integer $m$ such that every $n$-vertex $K_4$-free graph contains an induced triangle-free subgraph on at least $m$ vertices. The problem asks to determine the order of growth of $f(n)$.

QUICK LITERATURE/CONTEXT CHECK

The prompt states that $f(n)=n^{1/2+o(1)}$ is known and records the best bounds (up to polylogarithmic factors): \[ \Omega\!\left(\frac{\sqrt{n\log n}}{\log\log n}\right)\ \le\ f(n)\ \le\ O\!\left(\sqrt{n}\,\log n\right). \] Earlier work gave weaker polylogarithmic factors in the upper bound (e.g. $\sqrt{n}(\log n)^{120}$), later improved to $O(\sqrt{n}\log n)$. The ErdosProblems page lists the problem as open in the sense that the precise polylogarithmic factors (and constant-order behavior) are not settled.

ATTACK PLAN

A robust baseline is to prove the "$\sqrt n$" lower bound directly. The key structural fact in $K_4$-free graphs is that neighborhoods are triangle-free: if $v\in V(G)$, then $G[N(v)]$ contains no triangle (else together with $v$ it would form a $K_4$). Thus either there is a vertex of large degree (yielding a large triangle-free induced neighborhood), or all degrees are small, in which case a greedy bound produces a large independent set (which is triangle-free).

WORK

Remarks toward the stated best-known bounds.

The proof above explains the "$\sqrt n$" phenomenon: it is essentially forced by the dichotomy "large degree gives large triangle-free neighborhood" vs "bounded degree gives large independent set." Improving the lower bound by the factor $\sqrt{\log n}/\log\log n$ and constructing $K_4$-free graphs with no induced triangle-free subgraph larger than $O(\sqrt{n}\log n)$ requires substantially deeper probabilistic and Ramsey-theoretic tools (e.g. the triangle-free process, dependent random choice, and container-type arguments), beyond what is reproduced here.

VERIFICATION

• The neighborhood-triangle argument is correct: a triangle inside $N(v)$ would create a $K_4$ with $v$.
• The greedy independent-set bound $\alpha(G)\ge n/(\Delta+1)$ is standard and holds for all finite graphs.
• The two cases cover all graphs and produce an induced triangle-free subgraph either as a neighborhood subgraph or as an independent set.

FINAL

UNRESOLVED

1. Where and why the attempt fails. The problem asks for the true asymptotic order (including the correct polylogarithmic factor) of $f(n)$. The elementary argument here only proves the baseline $f(n)\ge \lfloor\sqrt n\rfloor$. Closing the gap between the best known lower bound $\Omega(\sqrt{n\log n}/\log\log n)$ and the best known upper bound $O(\sqrt n\log n)$ appears to require sophisticated probabilistic constructions and/or new structural ideas about $K_4$-free graphs and induced triangle-free subgraphs.

2. Strongest partial result proved here. A complete proof that $f(n)\ge \lfloor\sqrt n\rfloor$ (Theorem Theorem (Elementary lower bound)).

3. Most plausible next ideas. To improve the lower bound, one needs a stronger dichotomy than "large degree vs greedy independent set," likely using information about triangle structure in $K_4$-free graphs and refined bounds on large triangle-free induced subgraphs (e.g. Shearer-type entropy methods). To improve the upper bound, one needs an explicit or probabilistic construction of $K_4$-free graphs in which every induced subgraph on $m$ vertices contains a triangle for $m$ as large as possible (currently $m$ about $\sqrt n\log n$).

4. Small cases / computations. For small $n$, $f(n)$ can in principle be computed by brute force over $K_4$-free graphs, but this grows rapidly. Theorem Theorem (Elementary lower bound) is consistent with the small-$n$ regime and provides a universally valid baseline.

COMPLETION ESTIMATE

COMPLETION ESTIMATE: 45%.