Erdős problem 1036 · problems.science

Let $G$ be a graph on $n$ vertices which does not contain a trivial (empty or complete) graph on more than $c\log n$ vertices. Must $G$ contain at least $2^{\Omega_c(n)}$ many induced subgraphs which are not pairwise isomorphic?

Result history

Published changes, performers, checks, and later corrections.

No result history yet

No proposed change is retained for this Problem, so there is nothing to show a decision on.

Correction history

No correction history

Technical detailsExact roots, source, and retained record identifiers

Problem row: sha256:10d051082370088d1874aed3a31ace5aa90c526ea4aa38049d07686dc084abcd
Metadata: sha256:d522768cca6196771811425d2c5e0aa04a29fbd64f3cd2cb908ed491e8dbfa2a
Observation: sha256:8c823d621b7e1256c8e47c60a5f1c54c016a5507e6f27b2bab537f6f5f232067
Content: sha256:c3587bd2853f519cfb72124196b047cb516d56c33834a8c02ddbaeb664c5dfa3

Repository: sha256:a956b84c437202e5a02cc9e036a621bd14a302b34a75758115730bdbb77c52a4
Projection: sha256:c9d14c459c518937e758918b5897dc3b22f1a55f07739afe99502f5b046c907a
Source commit: 2415f78e850aeee50afdca525c6f2e0ea606f207

Upstream source Inspect records Source JSON

Result history

Correction history

Exact provenance

Search problems.science