Thrackle
A thrackle is an embedding of a graph in the plane, such that each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be transverse.[1]
Linear thrackles
A linear thrackle is a thrackle drawn in such a way that its edges are straight line segments. As Paul Erdős observed, every linear thrackle has at most as many edges as vertices. If a vertex v is connected to three or more edges vw, vx, and vy, at least one of those edges (say vw) lies on a line that separates two other edges. Then, w must have degree one, because no line segment ending at w, other than vw, can touch both vx and vy. Removing w and vw produces a smaller thrackle, without changing the difference between the numbers of edges and vertices. After removals like this lead to a thrackle in which every vertex has at most two neighbors, by the handshaking lemma the number of edges is at most the number of vertices.[2] Based on Erdős' proof, one can infer that every linear thrackle is a pseudoforest. Every cycle of odd length may be arranged to form a linear thrackle, but this is not possible for an even-length cycle, because if one edge of the cycle is chosen arbitrarily then the other cycle vertices must lie alternatingly on opposite sides of the line through this edge.
Micha Perles provided another simple proof that linear thrackles have at most n edges, based on the fact that in a linear thrackle every edge has an endpoint at which the edges span an angle of at most 180°, and for which it is the most clockwise edge within this span. For, if not, there would be two edges, incident to opposite endpoints of the edge and lying on opposite sides of the line through the edge, which could not cross each other. But each vertex can only have this property with respect to a single edge, so the number of edges is at most equal to the number of vertices.[3]
As Erdős also observed, the set of pairs of points realizing the diameter of a point set must form a linear thrackle: no two diameters can be disjoint from each other, because if they were then their four endpoints would have a pair at farther distance apart than the two disjoint edges. For this reason, every set of n points in the plane can have at most n diametral pairs, answering a question posed in 1934 by Heinz Hopf and Erika Pannwitz.[4] Andrew Vázsonyi conjectured bounds on the number of diameter pairs in higher dimensions, generalizing this problem.[2]
In computational geometry, the method of rotating calipers can be used to form a linear thrackle from any set of points in convex position, by connecting pairs of points that support parallel lines tangent to the convex hull of the points.[5] This graph contains as a subgraph the thrackle of diameter pairs.[6]
The diameters of the Reinhardt polygons form linear thrackles. An enumeration of linear thrackles may be used to solve the biggest little polygon problem, of finding an n-gon with maximum area relative to its diameter.[7]
Thrackle conjecture
John H. Conway conjectured that, in any thrackle, the number of edges is at most equal to the number of vertices. Conway himself used the terminology paths and spots (for edges and vertices respectively), so Conway's thrackle conjecture was originally stated in the form every thrackle has at least as many spots as paths. Conway offered a $1000 prize for proving or disproving this conjecture, as part of a set of prize problems also including Conway's 99-graph problem, the minimum spacing of Danzer sets, and the winner of Sylver coinage after the move 16.[8]
Equivalently, the thrackle conjecture may be stated as every thrackle is a pseudoforest. More specifically, if the thrackle conjecture is true, the thrackles may be exactly characterized by a result of Woodall: they are the pseudoforests in which there is no cycle of length four and at most one odd cycle.[1][9]
It has been proven that every cycle graph other than C4 has a thrackle embedding, which shows that the conjecture is sharp. That is, there are thrackles having the same number of spots as paths. At the other extreme, the worst-case scenario is that the number of spots is twice the number of paths; this is also attainable.
The thrackle conjecture is known to be true for thrackles drawn in such a way that every edge is an x-monotone curve, crossed at most once by every vertical line.[3]
Known bounds
Lovász, Pach & Szegedy (1997) proved that every bipartite thrackle is a planar graph, although not drawn in a planar way.[1] As a consequence, they show that every thrackleable graph with n vertices has at most 2n − 3 edges. Since then, this bound has been improved several times. First, it was improved to 3(n − 1)/2,[10] and another improvement led to a bound of roughly 1.428n.[11] Moreover, the method used to prove the latter result yields for any ε > 0 a finite algorithm that either improves the bound to (1 + ε)n or disproves the conjecture. The current record is due to Fulek & Pach (2017), who proved a bound of 1.3984n.[12]
If the conjecture is false, a minimal counterexample would have the form of two cycles sharing a vertex.[9] Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.
References
- ^ a b c Lovász, L.; Pach, J.; Szegedy, M. (1997), "On Conway's thrackle conjecture", Discrete and Computational Geometry, 18 (4): 369–376, doi:10.1007/PL00009322, MR 1476318. A preliminary version of these results was reviewed in O'Rourke, J. (1995), "Computational geometry column 26", ACM SIGACT News, 26 (2): 15–17, arXiv:cs/9908007, doi:10.1145/202840.202842.
- ^ a b Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
- ^ a b Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly, 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR 2812285.
- ^ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
- ^ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
- ^ For the fact that the rotating caliper graph contains all diameter pairs, see Shamos, Michael (1978), Computational Geometry (PDF), Doctoral dissertation, Yale University. For the fact that the diameter pairs form a thrackle, see, e.g., Pach & Sterling (2011).
- ^ Graham, R. L. (1975), "The largest small hexagon" (PDF), Journal of Combinatorial Theory, Series A, 18 (2): 165–170, doi:10.1016/0097-3165(75)90004-7.
- ^ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
- ^ a b Woodall, D. R. (1969), "Thrackles and deadlock", in Welsh, D. J. A. (ed.), Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR 0277421.
- ^ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi:10.1007/PL00009495, MR 1739605.
- ^ Fulek, R.; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry, 44 (6–7): 345–355, arXiv:1002.3904, doi:10.1007/978-3-642-18469-7_21, MR 2785903.
- ^ Fulek, R.; Pach, J. (2017), "Thrackles: An improved upper bound", Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10692, pp. 160–166, arXiv:1708.08037, doi:10.1007/978-3-319-73915-1_14, ISBN 978-3-319-73914-4.
External links
- thrackle.org—website about the problem