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?

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#22
  2. ResultNone
  3. Checks0

Search problems.science

Find a Problem, Result, source, or page