# P3016: Asymptotic growth of the maximum guaranteed order of a regular induced subgraph

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

## Problem

Erdős Problem 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\).

### Context

This problem concerns the extremal function for regular induced subgraphs in graph theory, a topic initiated by Erdős. The function \(F(n)\) measures the worst-case guarantee for finding large regular induced subgraphs. The best known upper bound, due to Alon, Krivelevich, and Sudakov (2007), establishes that \(F(n) = O\bigl(n^{1/2} (\log n)^{3/4}\bigr)\). The question of whether \(F(n)\) grows faster than any constant multiple of \(\log n\) remains open.

### Problem setup

- **Definition (A simple graph on a vertex set \(V\).** A simple graph on a vertex set \(V\) is an undirected graph without loops or multiple edges.
- **Definition (An induced subgraph of a graph \(G = (V, E)\) on a subset \(S \subseteq V\).** An induced subgraph of a graph \(G = (V, E)\) on a subset \(S \subseteq V\) is the graph with vertex set \(S\) whose edges are exactly those edges of \(G\) with both endpoints in \(S\).
- **Definition (A graph).** A graph is \(k\)-regular if every vertex has degree exactly \(k\).
- **Definition (For functions \(f, g : \mathbb{N} \to \mathbb{R}_{>0}\), we write \(f(n) = O(g(n))\) if there exist constants \(C > 0\) and \(n_0 \in \mathbb{N}\) such that \(f(n) \leq C \cdot g(n)\) for all \(n \geq n_0\).** For functions \(f, g : \mathbb{N} \to \mathbb{R}_{>0}\), we write \(f(n) = O(g(n))\) if there exist constants \(C > 0\) and \(n_0 \in \mathbb{N}\) such that \(f(n) \leq C \cdot g(n)\) for all \(n \geq n_0\).
- **Remark.** This problem concerns the extremal function for regular induced subgraphs in graph theory, a topic initiated by Erdős. The function \(F(n)\) measures the worst-case guarantee for finding large regular induced subgraphs. The best known upper bound, due to Alon, Krivelevich, and Sudakov (2007), establishes that \(F(n) = O\bigl(n^{1/2} (\log n)^{3/4}\bigr)\). The question of whether \(F(n)\) grows faster than any constant multiple of \(\log n\) remains open.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\).

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 82 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\). [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 82 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\).

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 82 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 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\).

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 82 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 82 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 82: For each positive integer \(n\), let \(F(n)\) denote the largest integer such that every finite simple graph on \(n\) vertices contains a regular induced subgraph with at least \(F(n)\) vertices. Here, a regular induced subgraph of a graph \(G\) is an induced subgraph that is \(k\)-regular for some non-negative integer \(k\), meaning every vertex in the subgraph has exactly \(k\) neighbors within the subgraph. Determine whether \(\displaystyle \frac{F(n)}{\log n} \to \infty\) as \(n \to \infty\). [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-82`, 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 82, maintained status record. Erdős Problems record 82, checked 2026-08-01. Problem 82; status field and linked bibliography https://www.erdosproblems.com/82
   - Also cited at Problem 82; 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 Asymptotic growth of the maximum guaranteed order of a regular induced subgraph: 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 82 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 Asymptotic growth of the maximum guaranteed order of a regular induced subgraph: 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 82. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/82.lean:L49; theorem erdos_82; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/82.lean#L49
   - 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 Asymptotic growth of the maximum guaranteed order of a regular induced subgraph: Supplies the pinned formal declaration whose human-readable editorial statement is published here.