Skip to content

Erdős problem 22

Let ϵ>0\epsilon > 0 and let nn be sufficiently large depending on ϵ\epsilon. Is there a graph on nn vertices with at least n2/8n^2/8 many edges which contains no K4K_4, such that the largest independent set has size at most ϵn\epsilon n?

Erdős Problems records this as proved.

No Repository has ruled on it here.

How far the record reaches4 of 6 stages
  1. Sourceerdos-problems
  2. StatementRetained
  3. Formal5 retained
  4. Resolutionproved
  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.

Where the source files it274 share a topic
None carries a Standing. Browse the topic.