Skip to content

Erdős problem 615

Does there exist some constant c>0c > 0 such that for all sufficiently large nn, if GG is a graph with nn vertices and at least (1/8c)n2(1/8 - c)n^2 edges then GG must contain either a K4K_4 or an independent set on at least n/lognn/\log n vertices?

Workspace

Open this exact Problem, source revision, and authority Repository in Workbench. This handoff does not clone, switch, upload, or execute anything.

Canvas

public preview
  1. Source#615
  2. ResultNone
  3. Checks0

Search problems.science

Find a Problem, Result, source, or page