Erdős Problem #1080
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Consider a bipartite graph on \(N\) vertices with one part of size about \(N^{2/3}\). Is there a fixed constant \(c>0\) such that every sufficiently large such graph with at least \(cN\) edges must contain a six-cycle \(C_6\)?
Erdős Problem #1080 asks this question. The answer is no. There are bipartite graphs with superlinearly many edges and without six-cycles.
A small example
The star \(K_{1,12}\) has thirteen vertices, twelve edges and no cycle of any length. It illustrates why a cycle is not automatic, but is not a disproof of the conjecture: a fixed \(c\) larger than one excludes this example. To refute an existential constant \(c\), we need graphs with \(e(G)/N\) becoming arbitrarily large while still avoiding \(C_6\).
What is known
De Caen and Székely (1992) constructed stronger examples avoiding both \(C_4\) and \(C_6\). With bipartition sizes \(n\) and \(\lfloor n^{2/3}\rfloor\), the maintained catalogue records more than
edges. Lazebnik, Ustimenko and Woldar (1994) increased the reported lower exponent to \(16/15+o(1)\). Since both exponents exceed one, a universal linear threshold cannot work.
The \(n\) in those papers is a part size, not the total number of vertices \(N=n+\lfloor n^{2/3}\rfloor\). Because \(N\sim n\), the superlinear conclusion still follows.
GCL's current state
Authenticated source audit #2351 distinguishes the actual asymptotic obstruction from the elementary finite star. The frozen Lean translation says the proposed forcing statement is false and points to an external Lean proof. Its own theorem body still contains an unproved placeholder. GCL has not kernel-replayed that proof.
What remains
Check the primary 1992 and 1994 constructions, their part-size constraints and their cycle exclusions; then replay the cited external Lean proof against immutable dependencies. No finite star establishes the asymptotic disproof.
Sources and claim boundaries
Erdős Problem #1080; de Caen–Székely (1992), pp. 135–142; Lazebnik–Ustimenko–Woldar (1994), published bipartite constructions; frozen formal translation; GCL return #2351. The external disproof is not a new GCL result. This draft is unaccepted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2351 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.