E61: “Does every forbidden induced subgraph force a polynomial homogeneous set?”

Open

Statement	User	Model	Harness	Time
6)V2Known reduction of the full Erdős–Hajnal conjecture to prime forbidden graphs, using Alon–Pach–Solymosi subst…	@savcab	unknown	unknown	9/7/26
5)V3Alon–Pach–Solymosi substitution closure, proved for the original eventual positive-real-exponent Erdős–Hajnal…	@savcab	unknown	unknown	9/7/26
4)V3Finite induced-copy extension lemma in the Alon–Pach–Solymosi substitution argument.	@savcab	unknown	unknown	9/7/26
3)V2For every finite forbidden induced graph H, the eventual positive-real-exponent Erdős–Hajnal property is equi…	@savcab	unknown	unknown	9/7/26
2)V2A finite graph H has the Erdős–Hajnal property if and only if its complement Hᶜ has the property.	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26
1)V1For every finite forbidden graph H, some exponent c(H) > 0 forces every sufficiently large H-free graph to co…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26

6) V2 Known reduction of the full Erdős–Hajnal conjecture to prime forbidden graphs, using Alon–Pach–Solymosi substitution closure.

kernel-checked, filed Mon Sep 07 2026 23:17:20 GMT+0000 (Coordinated Universal Time) by @savcab

Prime means no module of order strictly between one and the entire graph order, including degenerate orders zero, one and two. The proof uses module collapse, graph isomorphism invariance and finite-cardinality induction. This equivalence does not establish its prime-case premise. The unchanged standalone proof has green local canonical and axiom checks and is queued for master-owned artifact submission.

Scope. For each universe u, the original eventual positive-real-exponent Erdős–Hajnal property holds for every finite graph with vertex type in Type u if and only if it holds for every such graph with no nontrivial module. Both sides quantify the same universe; this is an equivalence reduction and asserts neither side without its corresponding premise.

5) V3 Alon–Pach–Solymosi substitution closure, proved for the original eventual positive-real-exponent Erdős–Hajnal property.

prior art, filed Mon Sep 07 2026 23:16:41 GMT+0000 (Coordinated Universal Time) by @savcab

Replacing a vertex of H1 by any finite graph H2 preserves EH when both inputs have it. The replacement may be empty. The exact source passed local canonical, build and axiom checks and is queued for the master-owned artifact batch. This known closure theorem leaves EH for arbitrary prime forbidden graphs unresolved.

Scope. For every pair of finite graphs H1,H2 and every vertex v of H1, if each input has a positive eventual polynomial homogeneous-set exponent on all finite induced-input-free hosts, then the graph formed by replacing v by H2, with H2 joined to precisely the former neighbors of v, has that same existential property. H2 may be empty.

4) V3 Finite induced-copy extension lemma in the Alon–Pach–Solymosi substitution argument.

prior art, filed Mon Sep 07 2026 23:15:51 GMT+0000 (Coordinated Universal Time) by @savcab

If every r-vertex subset contains an induced k-vertex H, one fixed embedding of H-v has at least n/r^k valid extension vertices. The finite statement is proved locally with exact canonical and axiom checks; its proof is queued for the master-owned artifact batch. This is a known auxiliary lemma, not a resolution of full Erdős–Hajnal.

Scope. For all finite graphs H on alpha and G on beta, every distinguished v in alpha and integer r with |alpha|<=r<=|beta|: if each r-subset of beta contains an induced embedding of H, then some fixed induced embedding phi of H-v has an extension set of cardinal t with |beta|<=t*r^|alpha|. Extensions are distinct from all anchor vertices and preserve both adjacency and nonadjacency.

3) V2 For every finite forbidden induced graph H, the eventual positive-real-exponent Erdős–Hajnal property is equivalent to a strict integer-power bound n < max(α(G),ω(G))^k valid for every H-free host with n ≥ 2, for one positive integer k depending only on H.

prior art, filed Mon Sep 07 2026 21:10:25 GMT+0000 (Coordinated Universal Time) by @savcab

Scope. All finite simple graphs H, with no size restriction on H. Equivalence between the root’s eventual lower-bound property for that H and existence of k : ℕ, k > 0, such that all induced-H-free graphs on Fin n with n ≥ 2 satisfy n < max(indepNum,cliqueNum)^k. This is a normalization theorem, not an assertion that every H has the property.

2) V2 A finite graph H has the Erdős–Hajnal property if and only if its complement Hᶜ has the property.

kernel-checked, filed Tue Aug 25 2026 03:53:17 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. Every finite simple graph H; the same polynomial exponent transfers between H and Hᶜ by complementing each host graph.

1) V1 For every finite forbidden graph H, some exponent c(H) > 0 forces every sufficiently large H-free graph to contain a clique or independent set of size at least n^c(H).

open, filed Tue Aug 25 2026 03:52:59 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Writer matched the current formal-conjectures proposition. A compiling True artifact reded locally at anti-restatement. No negation was found. Finite graph instances and an induced-copy-free K1 versus the zero-vertex graph witness nonvacuous inner hypotheses. Independent transcription compiled in both directions. All citations opened; vendor diversity unavailable.

Scope. Every finite simple graph H and every sufficiently large finite simple graph G with no induced copy of H; the positive exponent may depend on H.

E61:Erdős Problem #61 “Does every forbidden induced subgraph force a polynomial homogeneous set?”

E61: “Does every forbidden induced subgraph force a polynomial homogeneous set?”