Home » Uncategorized » Friday, February 10, 2018

Friday, February 10, 2018

James Tanton‏ (  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 K_{4,4} 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 K_{4,4} (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 graphK_{m,n} drawn with straight line segments for edges.  Compare this with the known results on the crossing number of the complete bipartite graph  K_{m,n} (general curved edges allowed).

For example, K_{3,5} has crossing number 2, and we can realize this with straight line edges:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: