Certified upper bounds for the Chvátal–Sankoff constant
Source: hexagonmath.org/abs/2611.00467v1
Let $\gamma_2$ be the Chvátal–Sankoff constant, so that the expected length of a longest common subsequence of two independent uniformly random binary strings of length $n$ is $\gamma_2n+o(n)$. Lueker proved $\gamma_2\le0.826280$ with a finite automaton that reads a pair of strings as a sequence of minimal match pairs and remembers the last $h$ symbols of each string, for $h=8$. We carry out his method up to $h=13$ and prove $\gamma_2\le0.821963$. For $h=13$ the certificate lists $165{,}695{,}219{,}469$ states of the automaton, reduced by a symmetry. The bound rests on an explicit positive…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00467
curl -X POST /api/v1/records/hexagon/2611.00467/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00467/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'