Erdős Problem #805
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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.
The question in plain language
Find g(n) for which some n-vertex graph has, in EVERY induced subgraph on g(n) vertices, BOTH a clique and an independent set of size >= log n. The existential choice of host G is outside the universal quantifier over induced g(n)-vertex subsets. Question especially asks g(n)=(log n)^3.
The required graph must contain, in each selected g(n)-vertex subset, BOTH a large clique and a large independent set. This is much stronger than a Ramsey disjunction that guarantees one of the two. The known very large construction does not resolve the original cubic-logarithmic target.
A small example
For empty Kbar4, every induced 3-vertex subgraph contains an independent set of size 3 but a clique of size only 1. For K4 the converse holds: clique of size 3 but independent number 1. Either fixture violates a simultaneous threshold 2. This explains why testing only one of the properties is inadequate.
This finite fixture tests the conventions. It does not certify any of the asymptotic or all-graphs assertions.
What is known
Maintained #805 OPEN: Erdős–Hajnal expected negative for cubic-log. Alon–Sudakov [AlSu07] rule out g(n)=c (log n)^3/loglog n for a positive c. Alon–Bucić–Sudakov [ABS21] exhibit graphs with g(n) at most 2^(2^((loglog n)^(1/2+o(1)))). The latter is much larger than (log n)^3 asymptotically; it does NOT settle cubic-log. Original 2007 and 2021 proofs remain primary-source obligations.
The distinctions between established partial theorems, original open parts, and disproved universal claims have been preserved. Historical publications are attributed, rather than presented as new GCL mathematics.
The logical order can be written as
$$
\exists G\quad \forall S\subseteq V(G),\ |S|=g(n): \quad\alpha(G[S])\geq\log n,\quad \omega(G[S])\geq\log n.
$$
Here the maximum clique number \(\omega\) and maximum independent-set size \(\alpha\) must satisfy the condition on the same induced subset. The open challenge concerns \(g(n)=(\log n)^3\).
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: open simultaneous local clique and independence cubic log gap. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Implement induced-subgraph homogeneous-number oracle (max clique and alpha) and check K4, empty Kbar4, C5. Verify logarithm exponent in ABS21 paper directly and compare quantitative scales without treating 2^(2^sqrtloglog) as (log n)^O(1).
Before protected admission the responsible editor must inspect full original proofs where not yet read, verify the executable finite example and mathematical notation, test actual public rendering, and record a critical review disposition. Local gate success alone is insufficient.
Sources and claim boundaries
- Erdos problem #805 and maintained source and bibliography, retrieved by web search 14 October 2026.
- Authenticated issue-bound return for #805, preserving source limitations and open proof obligations.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2076 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.