Another Brick in the Wall: A Computationally Assisted Proof of an Improved Upper Bound for Thrackles

Abstract

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 with Xu's framework, together with separate arguments for graphs containing triangles and disconnected graphs, we improve the known upper bound toward this conjecture to m≤1.385(n−1) for n≥4.

Improved lower bound for the two-way-assisted quantum capacity of the bosonic thermal-loss channel
Matthew Barber, Stefano Pirandola
arXiv1 Sep 2026PreprintarXiv licenceFull textMathematical physics Computational physicsarXiv
Geometric Realizations with Strong Self-Duality Part II: Diameter Graphs, Reuleaux Polyhedra, and Thrackles
Gábor Damásdi
arXiv5 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Surrogate-assisted multi-objective topology optimization design method for prefabricated large-span Suspen-Dome based on structural-mapping-method and improved-PGSA
Yuchen Dai, Ailin Zhang, Liuhaoxiang Wang +3
PLOS One2 Nov 2026Peer-reviewedCC BYFull textMaterials & polymers Algebra & number theoryPLOSEurope PMC
Fourfold Is Enough: Connected LEGO Models from One Brick Type
Joshua S. Gans
arXiv5 Sep 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
A cubulation of the associahedron using a torus-equivariant degeneration of the brick variety
Raj Gandhi, Gabe Udell
arXiv16 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{scoppetto2026another,
  title = {{Another Brick in the Wall: A Computationally Assisted Proof of an Improved Upper Bound for Thrackles}},
  author = {Truman Scoppetto},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17508},
  eprint = {2610.17508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17508},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Another Brick in the Wall: A Computationally Assisted Proof of an Improved Upper Bound for Thrackles
AU  - Truman Scoppetto
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17508
UR  - https://arxiv.org/abs/2610.17508
AB  - 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 with Xu's framework, together with separate arguments for graphs containing triangles and disconnected graphs, we improve the known upper bound toward this conjecture to m≤1.385(n−1) for n≥4.
ER  -

Abstract

Related

Cite