Skip to content

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

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.

Back to catalogue · Compendium introduction