ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Let $({\cal K}_1, {\cal K}_2)$ be two families of closed curves on a surface ${\cal S}$ , such that $|{\cal K}_1| = m$, $|{\cal K}_2| = n$, $m_0 \leq m \leq n$ , each curve in ${\cal K}_1$ intersects each curve in ${\cal K}_2$ , and no point of ${\cal S}$ is covered three times. When ${\cal S}$ is the plane, the projective plane, or the Klein bottle, we prove that the total number of intersections in ${\cal K}_1 \cup {\cal K}_2$ is at least 10mn/9 , 12mn/11 , and mn+10 -13 m 2 , respectively. Moreover, when m is close to n , the constants are improved. For instance, the constant for the plane, 10/9 , is improved to 8/5 , for n ≤ 5(m-1)/4 . Consequently, we prove lower bounds on the crossing number of the Cartesian product of two cycles, in the plane, projective plane, and the Klein bottle. All lower bounds are within small multiplicative factors from easily derived upper bounds. No general lower bound has been previously known, even on the plane.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009343
Permalink