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.,
Send comments to dan.archdeacon@uvm.edu
December 2003