Another Brick in the Wall: A Computationally Assisted Proof of an Improved Upper Bound for Thrackles
Let $G$ be a thrackle, where a thrackle is a graph drawing in which each edge meets every other edge exactly once, either at a vertex or at a crossing. It is conjectured that, for all thrackles, the number of edges is less than or equal to the number of vertices. Fulek and Pach created a program to determine whether or not a graph can be a thrackle. Through a reconstruction and improvement of their algorithm, we computationally prove a key dumbbell to be non-thrackleable. Using this exclusion, we improve Xu's 8-face half-edge bound from five to four. Finally, using this stronger restriction…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17508
curl -X POST /api/v1/records/arxiv/2610.17508/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17508/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'