Degree Transport and a Smaller Cubic Coefficient for Reset Thresholds
Source: hexagonmath.org/abs/2611.00172v1
We prove that every synchronizing complete deterministic finite automaton on $n\ge2$ states has reset threshold at most $\frac{8242}{49923}n^3+O(n^2)$. The cubic coefficient improves on Shitov's $8257/49923$ by $5/16641$. The main ingredient is a degree-transport inequality for graphs of state pairs mergeable by short words. It relates a long gap between consecutive minimum-rank word lengths to a large corank achievable in at most $n-1$ letters. Combining this relation with a discrete dual of Shitov's counting argument gives the improvement. An appendix makes the quadratic remainder explicit…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00172
curl -X POST /api/v1/records/hexagon/2611.00172/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00172/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'