# P3080: Four-cycle supersaturation just above the extremal threshold

- ID: `P3080`
- Reference: `c4-supersaturation-at-extremal-threshold`
- Page: https://theoremdb.org/statements/P3080
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(\operatorname{ex}(n,C_4)\) be the maximum number of edges in an \(n\)-vertex simple graph containing no cycle of length four. Prove or disprove that every \(n\)-vertex simple graph with more than \(\operatorname{ex}(n,C_4)\) edges contains at least \(c\sqrt n\) distinct copies of \(C_4\), for some absolute constant \(c>0\) and all sufficiently large \(n\).

### Context

Known frontier: The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open.

Open boundary: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.

### Problem setup

- **Definition (\(\operatorname{ex}(n,C_4)\)).** The extremal number is the largest edge count of an \(n\)-vertex \(C_4\)-free simple graph.
- **Definition (Copy of \(C_4\)).** A copy is a four-vertex subgraph whose four selected edges form a cycle; copies are counted by their vertex-edge sets.
- **Remark.** This is a supersaturation question at the first edge beyond the four-cycle-free extremal number.

### What counts as a solution

- Prove a universal \(c>0\) and threshold \(n_0\) giving the bound for every \(n\ge n_0\), or construct an infinite counterexample family with \(o(\sqrt n)\) four-cycles.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open. Exact unresolved remainder: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it. [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 conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open. Exact unresolved remainder: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.

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

The strongest neighboring result found in the cited sources is: The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open.

The exact unresolved remainder is: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.

A complete resolution must meet the following acceptance conditions:
- Prove a universal \(c>0\) and threshold \(n_0\) giving the bound for every \(n\ge n_0\), or construct an infinite counterexample family with \(o(\sqrt n)\) four-cycles.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open. Exact unresolved remainder: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: "Erdős Problem #60" C4 copies; "> ex(n;C_4)" sqrt n copies; C4 supersaturation extremal threshold 2025 2026
- Strongest checked neighboring result: The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open.
- Exact unresolved remainder: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.

### Other known results

- **Claim 2** (supported): The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open. [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): Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `c4-supersaturation-at-extremal-threshold`, 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 #60, Erdős Problems database (living entry), accessed 2026-08-01. Problem #60, OPEN banner, statement, remarks, and bibliography. Problem #60, OPEN banner, statement, remarks, and bibliography https://www.erdosproblems.com/60
   - Also cited at Thomas F. Bloom, Erdős Problem #60, Erdős Problems database (living entry), accessed 2026-08-01. Problem #60, 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 Four-cycle supersaturation just above the extremal threshold: This is the dated publication status for the canonical target Four-cycle supersaturation just above the extremal threshold.
   - Source named by the research packet.
2. <a id="reference-2"></a>Paul Erdős, “Some of my favourite unsolved problems,” A Tribute to Paul Erdős (1990), 467–478. Four-cycle supersaturation question https://mathscinet.ams.org/mathscinet/article?mr=1117038
   - 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 Four-cycle supersaturation just above the extremal threshold: Records an original formulation or early published statement of the problem.