# P3086: An explicit exponential lower bound for diagonal Ramsey numbers

- ID: `P3086`
- Reference: `constructive-exponential-ramsey-lower-bound`
- Page: https://theoremdb.org/statements/P3086
- Record maturity: Reviewed problem with recorded work

## Problem

Give a deterministic, explicit construction which, for infinitely many integers \(k\), produces a red-blue edge-colouring of \(K_{N_k}\) with no monochromatic \(K_k\), where \(N_k\ge C^k\) for one absolute constant \(C>1\).

### Context

Known frontier: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\).

Open boundary: Obtain any fixed exponential base greater than one by an explicit construction.

### Problem setup

- **Definition (Explicit construction).** A deterministic finite description or algorithm outputs the colouring from \(k\), with correctness proved without selecting a favourable random outcome.
- **Definition (Ramsey-avoiding colouring).** Neither colour class contains a complete graph on \(k\) vertices.
- **Remark.** The probabilistic method gives a stronger existential size, while known explicit constructions remain subexponential in the required sense.

### What counts as a solution

- Specify the construction, prove it avoids monochromatic \(K_k\), and prove \(N_k\ge C^k\) for a fixed \(C>1\) on an infinite sequence of \(k\).

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\). Exact unresolved remainder: Obtain any fixed exponential base greater than one by an explicit construction. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\). Exact unresolved remainder: Obtain any fixed exponential base greater than one by an explicit construction.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\).

The exact unresolved remainder is: Obtain any fixed exponential base greater than one by an explicit construction.

A complete resolution must meet the following acceptance conditions:
- Specify the construction, prove it avoids monochromatic \(K_k\), and prove \(N_k\ge C^k\) for a fixed \(C>1\) on an infinite sequence of \(k\).

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\). Exact unresolved remainder: Obtain any fixed exponential base greater than one by an explicit construction.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: "Erdős Problem #78" constructive Ramsey; explicit construction R(k) > C^k; explicit Ramsey graph logarithmic clique independent set 2025 2026
- Strongest checked neighboring result: The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\).
- Exact unresolved remainder: Obtain any fixed exponential base greater than one by an explicit construction.

### Other known results

- **Claim 2** (supported): The maintained record gives explicit constructions whose largest clique or independent set is at most \((\log n)^C\), which remains too large to yield \(N_k\ge C_0^k\). [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Obtain any fixed exponential base greater than one by an explicit construction.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `constructive-exponential-ramsey-lower-bound`, 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>Thomas F. Bloom, Erdős Problem #78, Erdős Problems database (living entry), accessed 2026-08-01. Problem #78, OPEN banner, statement, remarks, and bibliography. Problem #78, OPEN banner, statement, remarks, and bibliography https://www.erdosproblems.com/78
   - Also cited at Thomas F. Bloom, Erdős Problem #78, Erdős Problems database (living entry), accessed 2026-08-01. Problem #78, OPEN banner, statement, remarks, and bibliography
   - reference_database; reference source; checked 2026-08-01
   - Source use: original_summary
   - Supplies the maintained formulation, current open-status assessment, and recorded partial results.
   - Source used to assess the problem's recorded status.
   - For An explicit exponential lower bound for diagonal Ramsey numbers: This is the dated publication status for the canonical target An explicit exponential lower bound for diagonal Ramsey numbers.
   - Source named by the research packet.
2. <a id="reference-2"></a>Paul Erdős, “Some unsolved problems,” Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254. Probabilistic Ramsey lower bounds and explicit-construction question https://mathscinet.ams.org/mathscinet/article?mr=0177846
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Records an original formulation or early published statement of the problem.
   - Source used to assess the problem's recorded status.
   - For An explicit exponential lower bound for diagonal Ramsey numbers: Records an original formulation or early published statement of the problem.