Erdős problem #61 — wave 7c

Access date: 2026-07-27 UTC

Live page: <https://www.erdosproblems.com/61>

Verifier: erdos61_wave7c_verify.py

Claim labels

I use the requested labels throughout:

• (a) elementary-rigorous: a complete argument is given here.
• (b) rigorous modulo a named theorem: the exact theorem and primary source are named.
• (c) plausible/structural-unverified: a search miss, novelty assessment, or cost estimate, never a theorem.
• (d) computational-only: a finite exhaustive result established by the standalone checker.

0. Mandatory live-page gate

(d, page observation) Direct datacenter access was not used. I fetched the live page, its LaTeX view, and its discussion thread through the Bright Data browser route. The page rendered normally and says:

| live field | value |

|---|---:|

| problem status | OPEN |

| claimed proofs | 0 |

| interested in collaborating | None |

| currently working on this problem | None |

| likes | Dogmachine |

| looks difficult | Dogmachine |

| looks tractable | None |

| external database: formalised statement | Yes |

| could be formalised | None |

| working on formalisation | None |

| last edited | 10 April 2026 |

Thus the mandatory stop condition did not trigger.

Statement

The live LaTeX source begins verbatim:

> “For any graph \(H\) is there some \(c=c(H)>0\) such that every graph \(G\) on \(n\) vertices that does not contain \(H\) …”

The exact mathematical content of the complete statement is:

Here \(H\not\leq_{\mathrm{ind}}G\) means that \(G\) has no induced subgraph isomorphic to \(H\). This is the Erdős–Hajnal conjecture.

Results listed on the page

(b, as stated on the page and checked against the linked primary records)

• Erdős and Hajnal proved

\[ \max\{\omega(G),\alpha(G)\}\ge \exp(c_H\sqrt{\log n}) \]

for every fixed excluded induced graph \(H\).

• Bucić, Nguyen, Scott, and Seymour improved the general bound to

\[ \exp(c_H\sqrt{\log n\log\log n}). \]

• The conjecture is proved for every \(H\) with at most four vertices, for the bull, for \(C_5\), and for \(P_5\).
• Closure under vertex substitution then gives the conjecture for every graph on at most five vertices.
• For every path \(H\), the near-polynomial bound

\[ 2^{(\log n)^{1-o(1)}} \]

is known.

• The page points to Tung Nguyen's thesis for a detailed account and further special cases.

The primary records are Erdős–Hajnal, Ramsey-type theorems, DOI 10.1016/0166-218X(89)90045-090045-0); Bucić–Nguyen–Scott–Seymour, arXiv:2301.10147; Alon–Pach–Solymosi, DOI 10.1007/s004930100016; Chudnovsky–Safra, DOI 10.1016/j.jctb.2008.02.005; Chudnovsky–Scott–Seymour–Spirkl, arXiv:2102.04994; Nguyen–Scott–Seymour on \(P_5\), arXiv:2312.15333; and Nguyen–Scott–Seymour on all paths, arXiv:2307.15032.

All seven live comments

(d, page observation; mathematical correctness of comments is not assumed)

1. Alfaiz, 05:05 on 5 June 2026. Reports Huang–Ju–Zhou's E-graph result: \(P_5\) with one pendant edge added at its middle vertex has the Erdős–Hajnal property.

2. sammausberg, 16:09 on 25 April 2026. Explicitly says the linked AI-assisted notes do not claim a proof of Erdős–Hajnal. The five advertised finite statements concern: singleton-cut rows versus affine-cell covers; a first-splitter \(P_k\)-free equivalence; failure of two-anchor synchronization; success of coordinatewise split replacement; and a star-forest characterization of shattered rectangle traces. The comment links both a Drive note and Lean files.

3. Nat Sothanaphan, 17:11 on 25 April 2026. Says a “standard check” found no issue in those notes.

4. sammausberg, 17:15 on 25 April 2026. Thanks Nat for checking this and an earlier post.

5. Alfaiz, 08:54 on 8 December 2025. Summarizes Nguyen's thesis as treating \(P_5\), bounded VC-dimension, infinitely many prime graphs, the near-polynomial path bound, simultaneous hole/antihole exclusion, and simultaneous exclusion of subdivisions and their complements.

6. Alfaiz, 08:18 on 8 December 2025. Points to the all-paths near-polynomial result and notes its \(P_5\) conclusion; the page says it was updated in response.

7. zach hunter, 09:14 on 24 August 2025. Notes the still-open asymmetric variant asking for a polynomial clique or merely an unbounded independent set.

The discussion page itself warns that comments are user responsibility and are not verified. There are no proof claims hidden in the thread.

1. Current literature audit

Verified state

(b) The original general estimate and its \(\log\log\) improvement are exactly stated in the abstracts of Erdős–Hajnal 198990045-0) and arXiv:2301.10147.

(b) arXiv:2312.15333, now published in Proceedings of the London Mathematical Society 132(3), e70133 (2026), proves the conjecture for \(P_5\). Together with substitution closure, this gives all five-vertex graphs.

(b) The path estimate on the live page is supported by Induced subgraph density V. All paths approach Erdős–Hajnal, arXiv:2307.15032, whose abstract states the displayed \(2^{(\log n)^{1-o(1)}}\) bound.

(d, bibliographic audit) The live page's LaTeX bibliography currently attaches the key [NSS24] to On a problem of El-Zahar and Erdős, JCTB 165, 211–222. That paper's primary record concerns anticomplete subgraphs of large minimum degree and is not the all-path paper. The displayed path claim is correct, but its live bibliography key points to the wrong Nguyen–Scott–Seymour article.

(b) The June comment reflects version 1 of Huang–Ju–Zhou. The current version 2 of arXiv:2606.06258, revised 8 June 2026, proves two six-vertex cases: the E-graph and the Bird (a bull with a pendant edge added to one horn). The live problem's prose/comment does not yet mention the Bird addition.

(b) Nguyen–Scott–Seymour's arXiv:2307.06455 proves infinitely many prime graphs have the property. Its convenient sufficient condition requires every nontrivial prime induced subgraph to have both a degree-one vertex and a vertex of degree \(|H'|-2\).

(b) The July 2026 preprint arXiv:2607.09049 improves the quantitative exponent for graphs of bounded VC-dimension. It does not settle the unrestricted fixed-\(H\) conjecture.

Why \(C_6\) is a legitimate unresolved test case

(a) \(C_6\) is prime (proved in Section 4 below) and every vertex has degree two. It therefore does not meet the sufficient condition in arXiv:2307.06455.

(b) Chudnovsky–Scott–Seymour–Spirkl prove that the pair

\(\{C_6,\overline{C_6}\}\) has the Erdős–Hajnal property; see Theorem 1.9 of DOI 10.1112/plms.12504. This means graphs excluding both patterns. It does not prove the single-forbidden \(C_6\) case.

(c) Targeted searches for C6, induced C6, Paley(17), the exact exponent \(\log 3/\log 17\), and “Erdős–Hajnal coefficient” found no primary source settling the single-\(C_6\) case or recording the construction below. This is a search miss, not a novelty claim.

2. Results obtained in this run

Define

write

for the largest admissible exponent in the page's normalization, and define

the finite level-four threshold

The following are the concrete outputs.

Main construction

(a) For every integer \(k\ge1\), there is an explicit induced-\(C_6\)-free graph \(G_k\) with

Specifically,

the \(k\)-fold lexicographic power of the Paley graph on \(\mathbb Z/17\mathbb Z\).

Consequently,

where

Thus any exponent that can hold in the Erdős–Hajnal statement for \(C_6\) is at most

This is an upper obstruction on the possible exponent, not a disproof of the conjecture.

Exact finite result

(b) \(T_{C_6}(4)=18\). The lower witness is \(P_{17}\); the upper bound is the classical theorem \(R(4,4)=18\) of Greenwood and Gleason, DOI 10.4153/CJM-1955-001-4.

(b) In particular, \(h_{C_6}(17)=3\): \(P_{17}\) supplies the upper bound, and \(R(3,3)=6\) supplies the universal lower bound.

Complete six-vertex level-four table

(d)+(b) Among the 156 isomorphism types \(H\) on six vertices, exactly 104 are absent as induced subgraphs of \(P_{17}\). For every one of these 104 types,

The exhaustive type table and its encoding are in Section 5.

3. The base graph \(P_{17}\)

Let

Define \(P_{17}\) on \(\mathbb Z_{17}\) by

Clique and stable-set number

(a) Every affine map \(x\mapsto a+qx\), with \(q\in Q\), is an automorphism. Hence every oriented edge can be mapped to \(0,1\).

The common neighbors of \(0,1\) are exactly

Their three pairwise differences are nonresidues modulo \(17\), so this common-neighbor set is independent. Therefore no edge can extend to a \(K_4\), and \(\omega(P_{17})\le3\). Since \(\{0,1,2\}\) is a triangle,

Multiplication by the nonsquare \(3\) sends residues to nonresidues, so \(x\mapsto3x\) is an isomorphism from \(P_{17}\) to its complement. Therefore

No induced \(C_6\)

(a) If an induced \(C_6\) existed, normalize one oriented cycle edge to \(x_0=0,x_1=1\). At each step choose a new vertex adjacent to its predecessor and nonadjacent to all earlier nonconsecutive vertices; at the last step also require adjacency back to \(0\). Direct residue arithmetic gives the complete frontier:

| new index | all admissible normalized tuples | count |

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

| \(2\) | \(013,\ 015,\ 01\,10,\ 01\,14\) | 4 |

| \(3\) | \(0137,\ 013\,11,\ 013\,12,\ 0156,\ 0157,\ 01\,10\,6,\ 01\,10\,11,\ 01\,10\,12,\ 01\,14\,6,\ 01\,14\,12\) | 10 |

| \(4\) | \(01376,\ 0157\,11,\ 01\,10\,67,\ 01\,10\,11\,7,\ 01\,14\,67,\ 01\,14\,12\,11\) | 6 |

| \(5\), closing to \(0\) | none | 0 |

Thus \(P_{17}\) has no induced \(C_6\). The verifier independently checks all

six-vertex subsets and finds no 2-regular induced six-vertex subgraph at all.

4. Why lexicographic powers stay \(C_6\)-free

\(C_6\) is prime

(a) Recall that a module \(M\) is a vertex set such that each vertex outside \(M\) is either complete or anticomplete to \(M\).

Suppose \(2\le |M|\le5\) is a module in \(C_6\). Since \(C_6\) is connected, some edge \(xy\) has \(x\in M\) and \(y\notin M\). The module property makes \(y\) adjacent to every vertex of \(M\). Since \(y\) has degree two, \(|M|=2\), and \(M\) consists of the two neighbors of \(y\). The other neighbor of either member of \(M\) is adjacent to that member and not the other, contradicting that \(M\) is a module. Hence \(C_6\) has no proper nontrivial module.

Prime-pattern substitution lemma

(a) Let \(H\) be prime. If a graph \(F\) and every substituted fiber \(J_v\) are induced-\(H\)-free, then the substitution \(F(J_v:v\in V(F))\) is induced-\(H\)-free.

Indeed, intersect a hypothetical induced copy of \(H\) with each fiber. Every such intersection is a module of the copy, because a vertex in another fiber is complete or anticomplete to the whole fiber. Primeness gives only two possibilities:

1. the whole copy lies in one fiber, contradicting that fiber's \(H\)-freeness; or

2. the copy uses at most one vertex per fiber, and its projection is an induced copy of \(H\) in \(F\), contradicting \(F\)'s \(H\)-freeness.

Taking \(H=C_6\), \(F=P_{17}\), and iterating proves that every \(P_{17}^{\circ k}\) is induced-\(C_6\)-free.

Homogeneous numbers multiply

(a) For lexicographic products,

For the clique identity, the occupied fibers project to a clique of \(F\), and each occupied fiber contributes at most \(\omega(J)\) vertices. Taking maximum cliques in maximum-clique fibers gives equality. The stable-set proof is identical.

Since \(\omega(P_{17})=\alpha(P_{17})=3\), induction yields

This completes the explicit infinite construction.

5. Exact six-vertex computation

Canonical encoding

For a graph on vertices \(0,\ldots,5\), put the adjacency bits in this order:

(d) Its canonical code is the least 15-bit integer over all \(720\) vertex permutations, printed as four hexadecimal digits. Orbit enumeration of all \(2^{15}=32\,768\) masks produces exactly 156 types.

The checker then canonicalizes every one of the \(\binom{17}{6}\) induced subgraphs of \(P_{17}\):

| class | count |

|---|---:|

| all six-vertex types | 156 |

| realized in \(P_{17}\) | 52 |

| omitted by \(P_{17}\) | 104 |

| omitted automatically because \(\omega(H)\ge4\) or \(\alpha(H)\ge4\) | 72 |

| additional omissions with \(\omega(H),\alpha(H)\le3\) | 32 |

The 32 nonautomatic omitted codes are

0268 0278 028f 0290 0296 029f 02ee 02f8
0398 0399 039f 03ba 03be 03fe
06cf 06d5 06df 06f4 0758 075b
07dc 07de 07fe 0fdc 0fdd 0fdf
1711 1713 1717 19fe 1bbc 3dfe

Their union with the 72 types characterized by

\(\max\{\omega(H),\alpha(H)\}\ge4\) is the exact 104-type table.

The distribution of all 104 omissions is:

| \((\omega(H),\alpha(H))\) | omitted types |

|---:|---:|

| \((1,6)\) | 1 |

| \((2,5)\) | 5 |

| \((2,4)\) | 17 |

| \((2,3)\) | 6 |

| \((3,4)\) | 13 |

| \((3,3)\) | 20 |

| \((3,2)\) | 6 |

| \((4,3)\) | 13 |

| \((4,2)\) | 17 |

| \((5,2)\) | 5 |

| \((6,1)\) | 1 |

The SHA-256 fingerprint of the sorted, space-separated 104-code list is

7be9cf4fd1b062c513a57507f3c17e24c2d463cb7df63d0848fac8ed0d63ba00

(d) Only four of the 104 omitted types are prime:

06d5 0758 075b 1bbc

Here 0758 is \(C_6\), 1bbc is \(\overline{C_6}\), and 06d5, 075b are a complementary pair. Thus the same lexicographic-power argument also applies to the other three prime omissions, conditional only on the displayed finite type check.

Why all 104 thresholds equal 18

(a)+(b) Let \(H\) be any type omitted by \(P_{17}\). Then \(P_{17}\) is induced-\(H\)-free and has no clique or stable set of size four, so

Greenwood and Gleason's \(R(4,4)=18\) says every graph on 18 vertices has a \(K_4\) or an independent four-set, with no forbidden-pattern hypothesis needed. Hence

and equality follows.

6. Independent verification

Run:

python runs/erdos61_wave7c_verify.py

The final completed run took 17.8 seconds on this VM. Salient output was:

P_17: 68 edges; 68 triangles; 68 independent triples
K4 count = 0; independent-4 count = 0; induced-C6 count = 0
normalized induced-cycle frontier sizes: [4, 10, 6, 0]

six-vertex types: 156
realized in P_17: 52
omitted by P_17: 104
automatic omissions: 72
extra omissions: 32
prime omitted codes: 06d5 0758 075b 1bbc

log(3)/log(17)
= 0.387761935038490075436199360734418646830673629443876242346756

R(3,4) nine-vertex CNF:
UNSAT, 210 clauses, 75,283 DPLL search nodes

(d) The script uses only the Python standard library. It does not use NetworkX, nauty, a SAT package, a graph catalogue, or downloaded data.

(d) As an independent check of the named \(R(4,4)\) upper bound, it constructs the 36 edge variables for a nine-vertex graph, adds:

• 84 clauses forbidding triangles, and
• 126 clauses forbidding independent four-sets,

and proves the 210-clause formula unsatisfiable with a from-scratch DPLL routine. Thus \(R(3,4)\le9\); the one-vertex Ramsey recurrence gives

The Paley graph supplies the matching lower bound.

7. Exact wall

The missing uniform lemma

(b) Bucić–Fox–Pham prove that Erdős–Hajnal is equivalent to the polynomial Rödl and viral formulations; see arXiv:2403.08303.

(a) Therefore a sufficient—and by that named theorem equivalent—missing lemma for the chosen \(C_6\) case is:

> There is \(d>0\) such that, for every \(0<\varepsilon<1/2\), every induced-\(C_6\)-free graph \(G\) has an induced set \(S\) of size at least \(\varepsilon^d|G|\) for which \(G[S]\) or \(\overline{G}[S]\) has maximum degree at most \(\varepsilon|S|\).

(c) No argument here proves this. The simultaneous \(\{C_6,\overline{C_6}\}\) theorem can use one forbidden pattern in the sparse regime and the other in the dense regime; a graph assumed only \(C_6\)-free lacks precisely that second synchronized exclusion. This is the structural gap, not a finite arithmetic gap.

(b) Without such a polynomial dependence, the best verified general guarantee remains

which is subpolynomial. The construction here supplies the other side,

but does not bridge the lower-bound gap.

A concrete heavier computation not run

(a) To improve the exponent using a single base graph with homogeneous number four, one would need an induced-\(C_6\)-free graph with

because \(\log 4/\log n<\log 3/\log17\) first holds at \(n=36\).

(d, exact instance size) A direct static SAT encoding at \(n=36\) would have:

| item | count |

|---|---:|

| edge variables | 630 |

| \(K_5/I_5\)-blocking clauses | 753,984 |

| induced-\(C_6\)-blocking clauses | 116,867,520 |

| total literal occurrences | 1,760,552,640 |

| packed 4-byte literals alone | 6.56 GiB |

The \(C_6\) count uses \(6!/|\operatorname{Aut}(C_6)|=60\) labelled patterns on each six-set. Actual CDCL memory would be substantially higher than the packed-literal floor.

(c, engineering estimate) A sensible lazy-cut/symmetry-broken pilot would need a 32–64 GiB machine and roughly 24–168 core-hours. A certifying sweep, especially an unsatisfiable one, should be budgeted at \(10^3\)–\(10^4\) core-hours until a pilot gives an empirical rate. I did not launch it on this box. Even a successful finite search would only improve the upper exponent; it could not prove the conjectured positive lower exponent.

Conclusion

(a) The strongest verified output is the explicit infinite family

with every \(G_k\) induced-\(C_6\)-free.

(a)+(b) This yields the rigorous exponent obstruction \(c_{\mathrm{EH}}(C_6)\le\log_{17}3\) and the exact finite value \(T_{C_6}(4)=18\), the latter using the named Ramsey theorem.

(d) The computation also gives \(T_H(4)=18\) for exactly 104 of the 156 six-vertex isomorphism types.

(c) No claim of novelty or of resolving Erdős problem #61 is made.

PARTIAL: Explicit induced-C6-free lexicographic powers have 17^k vertices and homogeneous number 3^k, giving c_EH(C6) <= log_17(3), with T_C6(4)=18 and an exact 104-type six-vertex threshold table; the uniform polynomial lower bound remains open.