Delphi.science

Erdős Problem 766: the Dirac–Erdős bound

Source: github.com/VictorLiwentao/fc-palomar-proofs/tree/2d98cec293…

Wentao Li

Palomar Registrypalomar/PALOMAR-2026-11-19-000006Nov 19, 2026math.COscore 0

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.

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'