Small meshes of curves and their role in the analysis of optimal meshes (Q1869201)

An \((m,n)\)-mesh is a pair \((\mathcal{B},\mathcal{R})\) of families of closed curves in the plane, of sizes \(m\) and \(n\), respectively, such that every curve in \(\mathcal{B}\) intersects every curve in \(\mathcal{R}\). Let \(i^*(m,n)\) denote the minimum number of intersections in an \((m,n)\)-mesh. \textit{R. B. Richter} and \textit{C. Thomassen} [Discrete Comput. Geom. 13, 149-159 (1995; Zbl 0820.05015)] proved that the crossing number \(cr(C_m \times C_n)\) of the Cartesian product of the cycles of lengths \(m\) and \(n\) satisfies \(cr(C_m \times C_n) \geq i^*(m,n) - mn\) and that the exact value of \(i^*(m,n)\) for certain small values of \(m,n\) yields the exact value of \(cr(C_m \times C_n)\). \textit{F. Shahrokhi} et al. [Discrete Comput. Geom. 19, 237-247 (1998; Zbl 0929.05023)] proved that \(i^*(m,n) \geq \frac{12}{7} mn\) for \(n\) sufficiently close to \(m\). In the present paper, the author gives an improvement of the lower bound \(\frac{12}{7}m^2\) on \(i^*(m,m)\), showing that, for each \(\varepsilon> 0\), there exists an \(M(\varepsilon)\) such that \(i^*(m,m) \geq (\frac{31}{18} - \varepsilon)m^2\) for every \(m\geq M(\varepsilon)\). The proof is based on a deeper analysis of the nature of the intersections in certain small \((3,k)\)-meshes.