# P43: Erdős-Hajnal conjecture

- ID: `P43`
- Reference: `erdos-hajnal-conjecture`
- Page: https://theoremdb.org/statements/P43
- Record maturity: Reviewed problem with recorded work

## Problem

For every finite graph \(H\), there exists \(c(H)>0\) such that every \(H\)-free graph on \(n\) vertices contains a clique or an independent set of size at least \(n^{c(H)}\), where \(H\)-free means having no induced copy of \(H\).

### Context

Forbidding one induced pattern is conjectured to improve the logarithmic homogeneous sets supplied by general Ramsey theory to polynomial size.

### Problem setup

- **Definition (An induced copy preserves both edges and nonedges among its selected vertices).** An induced copy preserves both edges and nonedges among its selected vertices.
- **Definition (A clique has every possible edge, while an independent set has none).** A clique has every possible edge, while an independent set has none.
- **Remark.** Forbidding one induced pattern is conjectured to improve the logarithmic homogeneous sets supplied by general Ramsey theory to polynomial size.

### What counts as a solution

- Prove the polynomial-size homogeneous-set bound for every fixed forbidden induced graph H, or give a fixed H and an infinite family of H-free graphs whose largest cliques and independent sets are smaller than n^c for every positive c.

## Status

Unresolved in this packet after the dated source check. Strongest checked result: Huang, Ju, and Zhou prove the Erdős-Hajnal property for the E-graph and Bird forbidden-induced-subgraph classes, extending recent five-vertex-path and bull cases. The assertion for every fixed H remains open. Exact unresolved remainder: Prove a polynomial-size clique or independent set for every fixed forbidden induced graph H, or give one fixed H and an H-free family violating every positive power bound. [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Dated status and exact unresolved remainder).** Unresolved in this packet after the dated source check. Strongest checked result: Huang, Ju, and Zhou prove the Erdős-Hajnal property for the E-graph and Bird forbidden-induced-subgraph classes, extending recent five-vertex-path and bull cases. The assertion for every fixed H remains open. Exact unresolved remainder: Prove a polynomial-size clique or independent set for every fixed forbidden induced graph H, or give one fixed H and an H-free family violating every positive power bound.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

Strongest checked result: Huang, Ju, and Zhou prove the Erdős-Hajnal property for the E-graph and Bird forbidden-induced-subgraph classes, extending recent five-vertex-path and bull cases. The assertion for every fixed H remains open.

Exact unresolved remainder: Prove a polynomial-size clique or independent set for every fixed forbidden induced graph H, or give one fixed H and an H-free family violating every positive power bound.

### Background and intake notes

- Original intake status: The cited 2026 paper proves new cases of the Erdős-Hajnal conjecture while treating the general assertion as open. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.
- The formulation and status were checked against the cited 2026 paper on 2026-07-22.
- The conjecture is now known for every graph H on at most five vertices and for further special families.

### Open directions

- **Route 1** (reported): Prove the polynomial-size homogeneous-set bound for every fixed forbidden induced graph H, or give a fixed H and an infinite family of H-free graphs whose largest cliques and independent sets are smaller than n^c for every positive c. [1](#reference-1)

### Computational notes

- Finite graph searches can verify fixed H and bounded n without establishing an asymptotic exponent.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-hajnal-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Shenwei Huang, Yiao Ju, and Yidong Zhou, “Erdős-Hajnal beyond the five-vertex path”. arXiv:2606.06258 (2026). Shenwei Huang, Yiao Ju, and Yidong Zhou, arXiv:2606.06258, abstract https://arxiv.org/abs/2606.06258
   - Also cited at abstract and main theorems for the E-graph and Bird
   - Also cited at Editorial research route recorded 2026-07-31
   - preprint; primary source; arXiv:2606.06258, checked 2026-07-31; checked 2026-07-31
   - Source use: original_summary
   - The cited 2026 paper proves new cases of the Erdős-Hajnal conjecture while treating the general assertion as open. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - Adds two current special cases while leaving the universal forbidden-graph statement open.
   - Source named by the research packet.