[#P43] Erdős-Hajnal conjecture

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\).

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Context

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

2Remarks

Remark 1. An induced copy preserves both edges and nonedges among its selected vertices.

Remark 2. A clique has every possible edge, while an independent set has none.

3What 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.

1Status

Saved packet · July 31, 2026

What counts as a solution

Saved packet status (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.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem For Erdős-Hajnal conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details 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. Open full record →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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] Relevance to this problem For Erdős-Hajnal conjecture, record erdos-hajnal-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. 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. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

Notes and companion material

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-31. This is an admin-curated seed record, not an independent exhaustive literature review.

The conjecture is now known for every graph H on at most five vertices and for further special families.

Computational notes

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

2See also

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Erdős-Hajnal conjecture.” TheoremDB. P43. Problem statement; statement text SHA-256 349a864dd6e53069a2efe2491795d7f5656bbcb46d2a3cdc5ac674ed662eb7df. https://theoremdb.org/statement/?ref=P43

BibTeX

@misc{theoremdb-problem-349a864dd6e53069a2efe2491795d7f5656bbcb46d2a3cdc5ac674ed662eb7df,
  title = {{Erdős-Hajnal conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 349a864dd6e53069a2efe2491795d7f5656bbcb46d2a3cdc5ac674ed662eb7df},
  url = {https://theoremdb.org/statement/?ref=P43}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from arxiv.org^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. 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. ↗preprint · primary source · arXiv:2606.06258, checked 2026-07-31 · checked 2026-07-31Source 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.Also cited at abstract and main theorems for the E-graph and Bird.Also cited at Editorial research route recorded 2026-07-31.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.

An original CC0 restatement prepared by TheoremDB maintainers.

[#P43] Erdős-Hajnal conjecture

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance