Skip to content

Erdős problem 1036

Start work

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

Erdős Problems records this as proved (Lean).

No Repository has ruled on it here.

How far the record reaches4 of 6 stages
  1. Sourceerdos-problems
  2. StatementRetained
  3. Formal3 retained
  4. Resolutionproved (Lean)
  5. WorkNone recorded
  6. DecisionNone here
  7. The questionNot reached
What this record is missingWork

Nothing here has checked that finding.

Reproducing it here turns a report into evidence.

Open the work surface
Where the source files it274 share a topic
Graph Theory275
None carries a Standing. Browse the topic.
Start workOpen sources