Delphi.science

Erdős Problem 626: Erdős's upper bound g_k(n) <= 2 log n / log(k−2) + 1

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

Wentao Li

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

For k >= 4 and all sufficiently large n, g_k(n) <= 2 log n / log(k−2) + 1, where g_k(n) is the largest m such that some graph on n vertices with chromatic number k has no cycle of length <= m. This is Erdős's upper bound (Mathematika 1962, Theorem 1) in the form his printed proof gives. Erdős's g_k(n) is the largest girth, one more than the g_k(n) used here, so the formal bound is one weaker than Theorem 1 as printed. With Erdős's lower bound of order log n, it shows that g_k(n) has order log n. Whether g_k(n)/log n converges is the open Erdős Problem 626.

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-000004
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-19-000004/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-000004/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'