[#P3080] Four-cycle supersaturation just above the extremal threshold

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

Neutral schematic of an extremal graph with one highlighted added edge and the four-cycles it creates. — The objects and operations appearing in Four-cycle supersaturation just above the extremal threshold.

Agent access

Work in ChatGPT

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

Definitions and notation

1Context

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.

2Problem setup

Definition 1 (\(\operatorname{ex}(n,C_4)\)). The extremal number is the largest edge count of an \(n\)-vertex \(C_4\)-free simple graph.

Definition 2 (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 1. This is a supersaturation question at the first edge beyond the four-cycle-free extremal number.

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

1Status

Saved packet · August 1, 2026

What counts as a solution

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

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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][2] Relevance to this problem This is the dated publication status for the canonical target Four-cycle supersaturation just above the extremal threshold. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details 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. Open full record →
The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open.^[1][2] Relevance to this problem Locates the present research frontier immediately below Four-cycle supersaturation just above the extremal threshold. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The conjecture is proved when \(n=q^2+q+1\) for an even integer \(q\); the general orders remain open. This leaves the following boundary unresolved: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 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][2] Relevance to this problem Documents why Four-cycle supersaturation just above the extremal threshold was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across source collection and its cited primary literature, Crossref/arXiv or MathSciNet stable records, TheoremDB published, prospecting, formal-conjecture, packet, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - "Erdős Problem #60" C4 copies - "> ex(n;C_4)" sqrt n copies - C4 supersaturation extremal threshold 2025 2026 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. Related: Claim 1 Open full record →
Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it. Relevance to this problem Turns the remaining uncertainty in Four-cycle supersaturation just above the extremal threshold into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Establish the \(\Omega(\sqrt n)\) count uniformly for all sufficiently large \(n\), or refute it. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - 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. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

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.

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.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemFour-cycle supersaturation just above the extremal threshold

All 3 recorded relations between these records and the problem

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

“Four-cycle supersaturation just above the extremal threshold.” TheoremDB. P3080. Problem statement; statement text SHA-256 6bc7a563e61c5a1a9d1bb34d7861852980abf6ff53f4c760b1bf4d40a181d71b. https://theoremdb.org/statement/?ref=P3080

BibTeX

@misc{theoremdb-problem-6bc7a563e61c5a1a9d1bb34d7861852980abf6ff53f4c760b1bf4d40a181d71b,
  title = {{Four-cycle supersaturation just above the extremal threshold}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 6bc7a563e61c5a1a9d1bb34d7861852980abf6ff53f4c760b1bf4d40a181d71b},
  url = {https://theoremdb.org/statement/?ref=P3080}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from erdosproblems.com^[1], current as of August 1, 2026.

1Lean verification

1References

Packet source. 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. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Supplies the maintained formulation, current open-status assessment, and recorded partial results.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.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.
Paul Erdős, “Some of my favourite unsolved problems,” A Tribute to Paul Erdős (1990), 467–478. Four-cycle supersaturation question. ↗journal article · primary source · checked 2026-08-01Source 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.

Original TheoremDB statement and summary based on citation-only scholarly sources; no source prose, proof, table, code, or figure is reproduced.

[#P3080] Four-cycle supersaturation just above the extremal threshold

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

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

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance