Erdős problem #802 — wave 7m

Access date: 2026-07-27 (UTC).

Outcome

The problem remains open. I obtained two verifiable partial outputs.

1. Exact finite regime. For every \(K_4\)-free graph \(G\) on \(n\leq 11\) vertices with average degree \(t>1\),

\[ \alpha(G)\ \geq\ \frac{1}{\ln 4}\frac{\ln t}{t}n. \]

This constant is sharp in this finite regime: equality holds for the complement of the Wagner graph, which has \((n,t,\alpha)=(8,4,2)\). The lower bound is [d] computational-only because completeness for \(8\leq n\leq11\) rests on nauty's isomorph-free generator and exact independence-number routine. The equality construction and all of its invariants have an elementary proof [a].

2. Reduction of the first open case. A recent theorem of Dhawan--Janzer--Methuku forces every hypothetical \(K_4\)-free counterexample sequence to contain increasingly large complete tripartite graphs. In a \(K_4\)-free graph, every such \(K_{q,q,q}\) yields a canonical three-way decomposition with

\[ \alpha(G)\geq q+\max_i\alpha(G[X_i]). \]

The decomposition is elementary [a]; the forcing statement is [b] rigorous modulo the cited 2025 theorem. This identifies the remaining obstruction as a quantitative “branch-or-combine” lemma described below.

This does not prove the required uniform asymptotic statement.

Claim labels

• [a] elementary-rigorous: a complete proof is given here.
• [b] rigorous-modulo-named-theorem: the deduction is complete assuming the precisely cited theorem.
• [c] plausible/structural-unverified: a proposed route or diagnosis, not a theorem.
• [d] computational-only: established by the stated finite computation, not a uniform theorem.

Step 0: live-page audit

I fetched the Cloudflare-protected page through the Bright Data browser path, then separately fetched its LaTeX view and discussion thread. The live page showed:

• status: OPEN;
• 0 claimed proofs;
• “Interested in collaborating: None”;
• “Currently working on this problem: None”;
• one comment, containing only a correction of a formerly duplicated word “graph”; the comment says the site has already incorporated the correction;
• last edited: 26 October 2025.

Thus none of the mandatory stop conditions applied.

Verbatim live statement

> Is it true that any \(K_r\)-free graph on \(n\) vertices with average degree \(t\) contains an independent set on

> \[ > \gg_r \frac{\log t}{t}n > \]

> many vertices?

Source: Erdős Problems #802, with the exact source text checked at the LaTeX view.

Results listed on the live page

The page attributes the conjecture to Ajtai, Erdős, Komlós, and Szemerédi and lists the following.

• They proved

\[ \alpha(G)\gg_r \frac{\log\log(t+1)}{t}n. \]

[b]

• Shearer improved this to

\[ \alpha(G)\gg_r \frac{\log t}{t\log\log(t+1)}n. \]

[b]

• Ajtai, Komlós, and Szemerédi proved the conjectured bound for \(r=3\). [b]
• Alon proved the conjectured bound under the stronger hypothesis that every vertex neighbourhood induces a graph of chromatic number at most \(r-2\). [b]

The page gives these primary references:

• M. Ajtai, P. Erdős, J. Komlós, E. Szemerédi, On Turán's theorem for sparse graphs, Combinatorica 1 (1981), 313--317.
• M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), 354--360.
• N. Alon, Independence numbers of locally sparse graphs and a Ramsey type problem, Random Structures & Algorithms 9 (1996), 271--278.
• J. B. Shearer, On the independence number of sparse graphs, Random Structures & Algorithms 7 (1995), 269--271.

Literature audit

I searched by the exact conjecture, the \(K_r\)-free average-degree formulation, and the named authors. I checked the following primary texts rather than inferring results from titles.

1. The 1981 AEKS paper defines \(f(n,t,p)\) exactly in this setting, states the proposed \((n/t)\log t\) bound, and explicitly says that it could not decide the case \(p=4\). Its Theorem 2 gives the \((n/t)\log\log t\) scale for fixed \(p\). [b]

2. Shearer's paper exists at DOI 10.1002/rsa.3240070305 and gives the extra \(1/\log\log t\) loss for \(K_r\)-free graphs. [b]

3. Alon's paper, Theorem 1.1, gives

\[ \alpha(G)\geq \frac{c}{\log(r+1)}\frac{n}{t}\log t \]

when every neighbourhood is \(r\)-colorable. [b]

4. Dutta--Mubayi--Subramanian, arXiv:1102.4856, Theorem 1.3, supplies a degree-sequence refinement but retains the factor \(1/\log\log D\); it does not close #802. [b]

5. A relevant result appeared after the live page's last edit. Dhawan--Janzer--Methuku, arXiv:2511.17191v2, prove the conjectured bound for every fixed 3-colorable forbidden graph \(F\), equivalently for \(K_{q,q,q}\)-free graphs with fixed \(q\). Their Theorem 1.6 states

\[ \alpha(G)\geq(1-\varepsilon)\frac{n\log d}{d} \]

for sufficiently large \(d\), and their introduction explicitly says that Shearer's bound remains the best general bound for \(K_r\)-free graphs. Since \(K_r\) is not 3-colorable for \(r\geq4\), this is genuine partial progress but not a solution of #802. [b]

6. Ajtai--Komlós--Szemerédi prove

\[ R(r,k)=O_r\!\left(\frac{k^{r-1}}{(\log k)^{r-2}}\right); \]

this is stated in the abstract of their 1980 paper, DOI 10.1016/0097-3165(80)90030-890030-8). I use it below only for a dense-regime reduction. [b]

7. As a check on the \(K_4\) dense regime, Gishboliner--Janzer--Sudakov, arXiv:2409.06650, Proposition 4.1, prove directly that a \(K_4\)-free \(n\)-vertex graph of average degree \(d\geq n^{2/3}\) has

\[ \alpha(G)=\Omega(d/n^{1/3}). \]

This is compatible with, but weaker for the present reduction than, the general Ramsey estimate above. [b]

I found no primary source claiming the clique-forbidden problem solved or falsified. In particular, the December 2025 paper is explicit that the general bound is still Shearer's.

Exact finite computation for the first open case \(r=4\)

Define

The following table is exact modulo nauty 2.8.8. An entry \(u\!-\!v:a\) means \(a_n(m)=a\) for every \(u\leq m\leq v\). “Classes” is the number of nonisomorphic \(K_4\)-free graphs. [d]

| \(n\) | classes | exact lower envelope \(m:a_n(m)\) |

|---:|---:|:---|

| 4 | 10 | \(0:4,\ 1:3,\ 2\!-\!5:2\) |

| 5 | 29 | \(0:5,\ 1:4,\ 2\!-\!3:3,\ 4\!-\!8:2\) |

| 6 | 120 | \(0:6,\ 1:5,\ 2:4,\ 3\!-\!5:3,\ 6\!-\!12:2\) |

| 7 | 685 | \(0:7,\ 1:6,\ 2:5,\ 3\!-\!4:4,\ 5\!-\!10:3,\ 11\!-\!15:2,\ 16:3\) |

| 8 | 6,431 | \(0:8,\ 1:7,\ 2:6,\ 3:5,\ 4\!-\!6:4,\ 7\!-\!15:3,\ 16\!-\!18:2,\ 19\!-\!21:3\) |

| 9 | 103,164 | \(0:9,\ 1:8,\ 2:7,\ 3:6,\ 4\!-\!5:5,\ 6\!-\!8:4,\ 9\!-\!27:3\) |

| 10 | 2,894,632 | \(0:10,\ 1:9,\ 2:8,\ 3:7,\ 4:6,\ 5\!-\!7:5,\ 8\!-\!13:4,\ 14\!-\!31:3,\ 32\!-\!33:4\) |

| 11 | 138,892,304 | \(0:11,\ 1:10,\ 2:9,\ 3:8,\ 4:7,\ 5\!-\!6:6,\ 7\!-\!9:5,\ 10\!-\!18:4,\ 19\!-\!36:3,\ 37\!-\!40:4\) |

The nonmonotonicity at the dense end is real: for example, \(a_{11}(36)=3\), but \(a_{11}(37)=4\). Deleting an edge can increase the independence number, so monotonicity in \(m\) was not assumed. [d]

Sharp finite logarithmic bound

For each table entry set \(t=2m/n\) and, for \(t>1\), compute

The exhaustive table gives

attained at \((n,m,a_n(m))=(8,16,2)\). Hence

for every tabulated graph, and the constant cannot be raised. [d]

Elementary equality construction

Let \(W\) be the Wagner graph: start with the cycle \(C_8\) on vertices \(\mathbb Z/8\mathbb Z\) and add the four antipodal edges \(i(i+4)\). Let \(G=\overline W\).

• \(W\) has \(8+4=12\) edges, so \(G\) has \(28-12=16\) edges and average degree \(4\). [a]
• \(W\) is triangle-free: the cycle has no triangle, and the endpoints of an antipodal chord have no common neighbour. Thus \(\alpha(G)=\omega(W)=2\). [a]
• Any independent 4-set in \(C_8\) would have to alternate around the cycle, hence would be one of its two bipartition classes. Each such class contains an antipodal edge of \(W\). On the other hand, \(W\) has an independent 3-set, for example \(\{0,2,5\}\). Therefore \(\alpha(W)=3\), so \(\omega(G)=3\) and \(G\) is \(K_4\)-free. [a]
• Consequently

\[ \frac{\alpha(G)t}{n\ln t} =\frac{2\cdot4}{8\ln4} =\frac1{\ln4}. \]

[a]

The graph6 certificate emitted by nauty is GQyurg; the standalone script decodes it itself and brute-force checks that it is isomorphic to this closed-form construction.

Reproduction and independent checks

The standalone checker is:

runs/erdos802_wave7m_reverify.py

Run:

python runs/erdos802_wave7m_reverify.py

or use --max-n 10 for a roughly four-second check. The default \(n=11\) run took about 123 seconds for the census on this VM. The script:

1. streams nauty-geng -kq n into nauty-countg -q --eh;

2. recomputes and checks the complete edge/independence table and total class counts;

3. independently exhausts all \(2^{21}\) labelled graphs on seven vertices using Python bit masks, finding 1,486,597 labelled \(K_4\)-free graphs and the same \(n=7\) frontier;

4. decodes graph6 itself and checks \((n,m,\alpha,\omega)\) for four witnesses;

5. uses a dependency-free \(8!\)-permutation isomorphism check for the Wagner-complement certificate;

6. verifies the logarithmic inequality at 80-decimal precision and checks the dense-regime exponent identities with exact rational arithmetic.

The binaries used were Debian nauty 2.8.8+ds-5:

nauty-geng
9730b53764bdb28ecd2fdf755fafbc76992050f39e5ea19bb7d91433a26583e9

nauty-countg
e1bb3b451c4b597fa2ec94d11acc4067ec2a5a0b7baa87ae15d6c5ee3b366bfc

The all-labelled \(n=7\) computation is independent of nauty, but the completeness claim for \(8\leq n\leq11\) is not: it relies on nauty correctly producing one representative of every isomorphism class and correctly computing maximum independent sets. This dependency is why the finite theorem is labelled [d], not [a].

I did not run the full \(n=12\) census. Ten permitted \(1/1000\) nauty shards averaged 4.334 seconds and 4.78 million classes per shard, projecting roughly 1.2 core-hours for generation and about 1.5 core-hours after independence counting; at a representative commodity rate of \(\$0.05\) per core-hour this is about \(\$0.08\). This is outside the requested few-minute run budget and, more importantly, another finite row cannot settle the uniform conjecture. [d]

Two rigorous reductions

1. The dense-degree range is already covered

The off-diagonal Ramsey upper bound

implies, by inversion, that every \(n\)-vertex \(K_r\)-free graph satisfies

for all sufficiently large \(n\). [b]

If

then \(t\leq n\) and \(\log t\leq\log n\) give

Choosing \(C_r\) large relative to the Ramsey constant proves the desired #802 bound in this range. [a] from the named Ramsey bound, hence overall [b]

Thus it suffices to study

For the first open case \(r=4\), the unresolved range may be restricted to

[b]

Also, bounded \(t>1\) cannot furnish a counterexample sequence: the elementary greedy/Turán bound \(\alpha(G)\geq n/(t+1)\) gives a positive constant multiple of \(n\log t/t\) on every fixed bounded interval. Hence any counterexample sequence must have \(t\to\infty\). [a]

2. A counterexample must be complete-tripartite-rich

Fix \(\varepsilon=1/2\). Dhawan--Janzer--Methuku's Theorem 1.6 says that, for every fixed \(q\), every sufficiently high-average-degree \(K_{q,q,q}\)-free graph satisfies

Their uniformity remark further states that their argument permits

for an absolute \(c>0\) when \(\varepsilon\) is fixed. [b]

Therefore, if #802 fails for a fixed \(r\), there is a \(K_r\)-free sequence for which

and every sufficiently late graph in that sequence must contain

Without using the uniformity remark, the still-rigorous qualitative conclusion is that the largest such \(q\) tends to infinity. [b]

For \(r=4\), this obstruction has extra structure.

Tripartite decomposition lemma. Suppose a \(K_4\)-free graph \(G\) contains a copy of \(K_{q,q,q}\) with classes \(A_1,A_2,A_3\). Then the \(A_i\) are independent, and the remaining vertices can be partitioned as \(X_1\cup X_2\cup X_3\) so that \(A_i\) is anticomplete to \(X_i\). Consequently,

[a]

Proof. If two vertices inside \(A_i\) were adjacent, adding one vertex from each of the other two classes would form a \(K_4\); hence \(A_i\) is independent. If a vertex \(v\) outside the three classes had a neighbour in every \(A_i\), one such neighbour from each class together with \(v\) would form a \(K_4\). Thus \(v\) is anticomplete to at least one \(A_i\); assign it to one corresponding \(X_i\). If \(I_i\) is independent in \(G[X_i]\), then \(A_i\cup I_i\) is independent in \(G\), giving the inequality. \(\square\)

This converts the post-2025 tripartite obstruction into an exact recursive structure for \(K_4\)-free candidates.

Precise wall

Let

when \(d(H)>1\). The new theorem handles the branch in which \(H\) is \(K_{q,q,q}\)-free. If \(H\) contains such a tripartite graph, the elementary lemma gives only

In the sparse part of the unresolved range, \(\Phi(H)\) can be arbitrarily larger than

\(q\asymp\sqrt{\log d/\log\log d}\). Moreover, the displayed decomposition alone does not ensure that any one \(X_i\) retains \(\Phi(H)-O(q)\): vertices and internal edges can be distributed so that passing to only the largest branch loses a constant fraction of the potential. Independent sets from different \(X_i\) also cannot automatically be united because of cross-edges. [a] as a limitation of the displayed information

A sufficient missing ingredient for this route is the following quantitative branch-or-combine lemma:

• either some \(X_i\) preserves the independence potential up to the additive gain \(q\), in the sense needed to induct on \(\Phi\);
• or the cross-edge pattern permits independent sets from two or three branches to be combined to total size \(\Omega(\Phi(H))\).

No such lemma is proved here, and I found no cited source supplying it. Its formulation is [c] plausible/structural-unverified. Proving it (with constants stable under iteration) would close the identified \(K_4\) obstruction; merely iterating \(q+\max_i\alpha(X_i)\) does not.

This also explains why the available standard machinery stalls:

• Shearer's uniform-random-independent-set argument loses exactly the factor \(\log\log t\); the 2025 paper explicitly notes that the same difficulty persists for general clique-free graphs. [b]
• Alon's method closes the problem when neighbourhoods have bounded chromatic number, but a \(K_4\)-free graph only guarantees triangle-free neighbourhoods; repeated Mycielski constructions show that triangle-free chromatic numbers are unbounded. [b]
• The new nibble theorem closes the \(K_{q,q,q}\)-free branch, but a hypothetical clique-free counterexample is forced into the complementary, tripartite-rich branch. [b]
• Finite enumeration through \(n=11\) gives a sharp concrete theorem and extremizer, but supplies no uniformity in \(n\) or \(t\). [d]

PARTIAL: exact \(K_4\)-free edge/independence frontiers through \(n=11\) prove the sharp finite bound \(\alpha\ge n\ln t/(t\ln4)\), and the open asymptotic case is reduced to a quantified complete-tripartite-rich branch needing a branch-or-combine lemma.