Four Questions about Drawing the Complete Graph
We ask four questions about drawings of the complete graph K_n in the plane. In a drawing non-adjacent edges are allowed to cross transversally at most once. An empty triangle in a drawing is a K_3 such that all the remaining vertices lie on one side of the triangle.
Question 1: What is the smallest number t(n) of empty triangles in a drawing of K_n?
An upper bound of t(n) at most 2n-4 is known.
The next problem is in the spirit of Ester Klein or of Ramsey. There exists smallest numbers m = Dr(K_n) such that every drawing of K_m contains at least one subdrawing of K_n with the maximum number n(n-1)(n-2)(n-3)/24 of crossings. It is known that Dr(K_5) is at least 11 and at most 113. See [HMS].
Question 2: Does there exist a drawing of K_11 such that every subdrawing of K_5 has only one or three crossings?
Let h(s,n) denote the minimum number of edges with at most s crossings in drawings of K_n. The following question is related to [HT].
Question 3: For which values of n is h(s,n) > 0? Is h(s,n) > 0 for n at most s?
The fourth question arises from [HM].
Question 4: Does there exist a drawing of K_n with the maximum number of crossings such that a) at most one edge is without a crossing, or b) no edge is without a crossing?
Harborth has a drawing of K_n (for each n) with two edges lacking crossings.
[HMS] H. Harborth, I. Mengersen, and R.H. Schelp, The drawing Ramsey number Dr(K_n), Australas. J. Combin. 11 (1995) 151-156.
[HT] H. Harborth and C. Thurmann, Minimum number of edges with at most s crossings in drawings of the complete graph, Congressus Numerantium 102 (1994) 83-90.
[HM] H. Harborth and I. Mengersen, Drawings of the complete graph with maximum number of crossings, Congressus Numerantium 88 (1992) 225-228.
Submitted by : Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany
Send comments to firstname.lastname@example.org and to email@example.com