Conway's Thrackle Conjecture
   HOME

TheInfoList



OR:

A thrackle is an
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group (mathematics), group that is a subgroup. When some object X is said to be embedded in another object Y ...
of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
in the plane in which 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, they must cross at their intersection point: the intersection must be ''
transverse Transverse may refer to: *Transverse engine, an engine in which the crankshaft is oriented side-to-side relative to the wheels of the vehicle *Transverse flute, a flute that is held horizontally * Transverse force (or ''Euler force''), the tangen ...
''.. A preliminary version of these results was reviewed in . A special case of thrackles, the linear thrackles, restrict the edges to be drawn as straight line segments. One method for constructing a linear thrackle with any given set of points as vertices is to form an edge between each farthest pair of points. For a linear thrackle, each connected component contains at most one cycle, from which it follows that the number of edges is at most equal to the number of vertices. John H. Conway conjectured more generally that every thrackle has at most as many edges as vertices. It is known that the number of edges is at most a constant times the number of vertices.


Linear thrackles

A linear thrackle is a thrackle drawn in such a way that its edges are straight line segments. As
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
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 In graph theory, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people ...
the number of edges is at most the number of vertices.. Based on Erdős' proof, one can infer that every linear thrackle is a
pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every Connected component (graph theory), connected com ...
. 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 Micha Asher Perles () is an Israeli mathematician working in geometry, a professor emeritus at the Hebrew University. He earned his Ph.D. in 1964 from the Hebrew University, under the supervision of Branko Grünbaum. His contributions include: *Th ...
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. As Erdős also observed, the set of pairs of points realizing the
diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
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 Heinz Hopf (19 November 1894 – 3 June 1971) was a German mathematician who worked on the fields of dynamical systems, topology and geometry. Early life and education Hopf was born in Gräbschen, German Empire (now , part of Wrocław, Poland) ...
and Erika Pannwitz.
Andrew Vázsonyi Andrew Vázsonyi (1916–2003), also known as Endre Weiszfeld and Zepartzatt Gozinto) was a Hungarian mathematician and operations researcher. He is known for Weiszfeld's algorithm for minimizing the sum of distances to a set of points, and for ...
conjectured bounds on the number of diameter pairs in higher dimensions, generalizing this problem. In computational geometry, the method of
rotating calipers In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter (computational geometry), diameter of a set of points. The method ...
can be used to form a linear thrackle from any set of points in
convex position In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the ot ...
, by connecting pairs of points that support parallel lines tangent to the
convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of the points. This graph contains as a subgraph the thrackle of diameter pairs. The diameters of the
Reinhardt polygon In geometry, a Reinhardt polygon is an equilateral polygon inscribed in a Reuleaux polygon. As in the regular polygons, each vertex of a Reinhardt polygon participates in at least one defining pair of the diameter of the polygon. Reinhardt poly ...
s 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..


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 In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices ...
, the minimum spacing of
Danzer set In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved. Formulation A ''D ...
s, and the winner of
Sylver coinage Sylver coinage is a mathematical game for two players, invented by John H. Conway. The two players take turns naming positive integers that are not the sum of nonnegative multiples of previously named integers. The player who names 1 loses. For i ...
after the move 16. Equivalently, the thrackle conjecture may be stated as ''every thrackle is a
pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every Connected component (graph theory), connected com ...
.'' 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.. It has been proved that every cycle graph other than ''C''4 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..


Known bounds

proved that every bipartite thrackle is a
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
, although not drawn in a planar way. As a consequence, they show that every thrackleable graph with ''n'' vertices has at most 2''n'' − 3 edges. Since then, this bound has been improved several times. First, it was improved to 3(''n'' − 1)/2, and another improvement led to a bound of roughly 1.428''n''.. 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 , who proved a bound of 1.393''n''. If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex. Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.


References

{{reflist


External links


thrackle.org
€”website about the problem Conjectures Topological graph theory Geometric intersection