Maximum number of edges in a thrackle
A thrackle is a drawing of a graph with $n$ vertices in the plane, edges drawn as smooth curves joining their endpoints, in which any two edges have exactly one common point, where their tangent lines differ. Equivalently, every two edges without a common endpoint cross exactly once, and edges with a common endpoint share no interior point.
Conway conjectured that a thrackle on $n$ vertices has at most $n$ edges; this is long known for straight-line thrackles. Lovász, Pach and Szegedy improved the upper bound from $O(n^{3/2})$ to $2n-3$, and Cairns and Nikolayevsky to $\frac{3}{2}(n-1)$. Cairns and Nikolayevsky also proposed that a thrackle on $n$ vertices drawn on a surface of genus $g$ has at most $n+2g$ edges.
Problem. What is the maximum number of edges of a thrackle on $n$ vertices?
Source: Conway (late 1960s); Problem 30 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- Conway's thrackle conjecture, graph drawing, The Open Problems Project, thrackle
References
@inproceedings{lovasz1995,
author = {Lov{\'a}sz, L{\'a}szl{\'o} and Pach, J{\'a}nos and Szegedy, Mario},
title = {On {Conway's} Thrackle Conjecture},
booktitle = {Proc. 11th Annu. ACM Sympos. Comput. Geom.},
year = {1995},
pages = {147--151},
}
@article{cairns2000,
author = {Cairns, G. and Nikolayevsky, Y.},
title = {Bounds for Generalized Thrackles},
journal = {Discrete Comput. Geom.},
volume = {23},
number = {2},
year = {2000},
pages = {191--206},
}
@book{brass2005,
author = {Brass, Peter and Moser, William and Pach, J{\'a}nos},
title = {Research Problems in Discrete Geometry},
publisher = {Springer},
address = {New York},
year = {2005},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01081, "Maximum number of edges in a thrackle", clopen.solutions.