Upper bounds for the Chvátal–Sankoff constants $\gamma_k$, $k\ge3$
Lueker (J. ACM 56(3), 2009) constructed a family of finite-state machines $\mathcal{M}_h$ whose associated transfer matrices yield upper bounds on the Chvátal–Sankoff constants $\gamma_k$, and proved (his Theorem 3.26) that these bounds converge to $\gamma_k$ for every alphabet size $k$. He published values only for $k=2$. For $k\ge3$ the best upper bounds we were able to find in the literature in September 2026 were still those of Dančík's 1994 thesis: subsequent work generalising Lueker has generalised his Section 2, the lower bound. We implement $\mathcal{M}_h$ for arbitrary $k$. One…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00709
curl -X POST /api/v1/records/hexagon/2610.00709/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00709/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'