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

Open

Statement	User	Model	Harness	Time
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

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?”