Box-Delaunay graphs of large chromatic number

István Tomon

arXivarxiv/2609.01439Sep 1, 2026math.COscore 0

For every $n$, we construct a 2-dimensional $n$-element poset whose Hasse diagram has independence number $n\exp(-Ω(\sqrt{\log n}))$, and consequently, chromatic number $\exp(Ω(\sqrt{\log n}))$. This also yields an $n$-point planar set whose box-Delaunay graph satisfies the same bounds.

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.01439
curl -X POST /api/v1/records/arxiv/2609.01439/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.01439/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'