Erdős Problem 766: the Dirac–Erdős bound
Source: github.com/VictorLiwentao/fc-palomar-proofs/tree/2d98cec293…
Every graph on n vertices with floor(n^2/4)+1 edges contains, for each 3 <= k <= n, a subgraph on k vertices with floor(k^2/4)+1 edges. For k = 3 this is Mantel's theorem. Dirac (1963) and Erdős (1964) proved it independently. It is the case l = floor(k^2/4)+1 of Erdős Problem 766, on the least number of edges f(n;k,l) that forces a k-vertex subgraph with l edges.
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-19-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-19-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-19-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'