How Often Must Curves Touch?



Suppose that we are given n simple closed curves in the plane such that each curve shares a point with every other curve, but no three curves share a common point. Two curves that share a point need not cross transversally—tangential intersections are allowed. Let f(n) denote the minimum number of intersections over all such families of curves.

It is obvious that f(n) is at least as large as the binomial coefficient C(n,2). It is also easy to construct examples that show f(n) is at most 2 C(n,2): take circles C_i of the same radius with centers perturbed a small distance epsilon_i from the origin. It is also known that f(4) = 6, f(5) = 12, and f(6) = 20.

Problem: Determine f(7).

Asymptotically:

Conjecture: Lim f(n)/C(n,2) = 2 (the limit is as n approaches infinity)

It is not hard to show that f(n+1) is at least ceiling[f(n) (n+1)/(n-1)]: in any realization of n+1 curves, count the number of induced intersections over all sub-realizations of n curves. In combination with f(6) = 20, this implies that the limit in the conjecture is at least 3/2.

I believe that these problems were first posed by Bruce Richter and Carsten Thomassen in [RT]. A partial result is given by Gelasio Salazar [S] who showed that if any two such curves intersect in at most k points (for a fixed value of k), then the above limit is 2. This includes many special cases; for example, when each curve is an ellipse, or when each curve is a piecewise-linear p-gon for fixed p.

References:

[RT] R.B. Richter and C. Thomassen, Intersections of curve systems and the crossing number of C_5 x C_5, Disc. Comp. Geom. 13 (1995) 149-159.

[S] G. Salazar, On the intersections of systems of curves, J. of Combin. Theory Ser. B 75 (1999) 56-60.


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003