James Tanton (@jamestanton on Twitter) posted the following tweet February 5, 2018:
“Connect each of N red dots to each of N blue dots on a page with straight line segments. Let I(N) be the least number of intersection points that might be seen. I(1) = 0, I(2) = 0, I(3) = 1, I(4) = ?”
Compare this with the crossing number problem for the complete bipartite graph
Note that James Tanton has insisted on straight line segments joining blue and red dots, and not allowed more general curves.
We can certainly draw the complete bipartite graph with 4 red and 4 blue vertices with straight line segments for edges that cross in at most 4 places:
Since the crossing number for (straight line segments not required for edges) is 4 we cannot do better with straight lines, so I(4)=4.
What might be a solution to the calculation of I(N) for different N, and how might this relate to the crossing number for complete bipartite graphs?
More generally we can ask what is the minimum possible number of crossings when we join m red dots to each of n blue dots using only straight line segments; that is, the complete bipartite graph drawn with straight line segments for edges. Compare this with the known results on the crossing number of the complete bipartite graph (general curved edges allowed).
For example, has crossing number 2, and we can realize this with straight line edges: