The board / graph theory / #804
Erdős Problem #804
DISPROVEDdatabase updated 2025-08-31
The statement as posed is false.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A graph `G` on `n` vertices in which every induced subgraph on `m` vertices has an independent set of size at least `t`.
`f m n` is maximal such that any graph on `n` vertices in which every induced subgraph on `m` vertices has an independent set of size at least \(\log n\) must contain an independent set of size at least `f m n`.
Let \(f(m,n)\) be maximal such that any graph on \(n\) vertices in which every induced subgraph on \(m\) vertices has an independent set of size at least \(\log n\) must contain an independent set of size at least \(f(n)\). Estimate \(f(n)\). In particular, is it true that \(f((\log n)^2,n) \geq n^{1/2-o(1)}\)? The answer is no: Alon and Sudakov [AlSu07] proved that in fact \[\frac{(\log n)^2}{\log\log n}\ll f((\log n)^2,n) \ll (\log n)^2.\]
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/804.Prizenone
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/804
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.