# P3004: The Erdős–Hajnal Conjecture on Polynomial Ramsey-Type Bounds

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

## Problem

Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$?

### Context

This problem asks whether the Erdős–Hajnal conjecture holds: that forbidding any fixed induced subgraph forces a polynomially large homogeneous set (clique or independent set), rather than merely the logarithmic bound guaranteed by Ramsey's theorem.

### Problem setup

- **Definition (A simple graph $G$ consists of a vertex set together with a set of undirected edges, with no loops and no multiple edges).** A simple graph $G$ consists of a vertex set together with a set of undirected edges, with no loops and no multiple edges.
- **Definition (A graph $G$).** A graph $G$ is $H$-free if there is no embedding of the vertices of $H$ into the vertices of $G$ that preserves both adjacency and non-adjacency (i.e., $H$ is not an induced subgraph of $G$).
- **Definition (The independence number $\alpha(G)$ of a graph $G$).** The independence number $\alpha(G)$ of a graph $G$ is the maximum cardinality of a set of vertices with no edges between them.
- **Definition (The clique number $\omega(G)$ of a graph $G$).** The clique number $\omega(G)$ of a graph $G$ is the maximum cardinality of a set of vertices in which every pair is joined by an edge.
- **Definition (An Erdős–Hajnal lower bound for $H$).** An Erdős–Hajnal lower bound for $H$ is a function $f$ such that for all sufficiently large $n$, every $n$-vertex $H$-free graph has either independence number or clique number at least $f(n)$.
- **Remark.** This problem asks whether the Erdős–Hajnal conjecture holds: that forbidding any fixed induced subgraph forces a polynomially large homogeneous set (clique or independent set), rather than merely the logarithmic bound guaranteed by Ramsey's theorem.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 61 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$? [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 61 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 61 as open. The unresolved remainder is the full displayed statement.

A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 61 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 61 was open at commit 8138974387d9030542daabe67faaa33eff9356f8.
- The pinned Formal Conjectures declaration was matched by problem number and source locator.
- The controlled TheoremDB source corpus was checked for an already published record with the same slug.

### Open directions

- **Route 1** (reported): Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 61: For a finite simple graph $H$, say that a simple graph $G$ is $H$\textit{-free} if $H$ does not appear as an induced subgraph of $G$. For a graph $G$, let $\alpha(G)$ denote the independence number of $G$ (the size of a largest independent set), and let $\omega(G)$ denote the clique number of $G$ (the size of a largest clique). For a function $f : \mathbb{N} \to \mathbb{R}$, say that $f$ is an \textit{Erdős–Hajnal lower bound} for $H$ if for all sufficiently large $n$, every $H$-free graph $G$ on $n$ vertices satisfies $\alpha(G) \geq f(n)$ or $\omega(G) \geq f(n)$. Does there exist, for every finite simple graph $H$, a constant $c > 0$ such that the function $n \mapsto n^{c}$ is an Erdős–Hajnal lower bound for $H$? [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-61`, 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>Erdős Problems database, Problem 61, maintained status record. Erdős Problems record 61, checked 2026-08-01. Problem 61; status field and linked bibliography https://www.erdosproblems.com/61
   - Also cited at Problem 61; status snapshot 8138974387d9030542daabe67faaa33eff9356f8
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Records the current open status and links the literature attached to this exact numbered problem.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - For The Erdős–Hajnal Conjecture on Polynomial Ramsey-Type Bounds: Records the current open status and links the literature attached to this exact numbered problem.
   - Source named by the research packet.
2. <a id="reference-2"></a>Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 61 entry in data/problems.yaml https://github.com/teorth/erdosproblems/blob/8138974387d9030542daabe67faaa33eff9356f8/data/problems.yaml
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Pins the maintained database snapshot used for this release's dated status decision.
   - Source used to assess the problem's recorded status.
   - For The Erdős–Hajnal Conjecture on Polynomial Ramsey-Type Bounds: Pins the maintained database snapshot used for this release's dated status decision.
3. <a id="reference-3"></a>Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 61. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/61.lean:L46; theorem erdos_61; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/61.lean#L46
   - reference_database; primary source; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1; checked 2026-07-31
   - Source use: original_summary
   - Supplies the pinned formal declaration whose human-readable editorial statement is published here.
   - Source used to assess the problem's recorded status.
   - For The Erdős–Hajnal Conjecture on Polynomial Ramsey-Type Bounds: Supplies the pinned formal declaration whose human-readable editorial statement is published here.