Skip to content

A Math Gift For All

December 26, 2019

Happy holidays to all.

Kathryn Farley is my dear wife. We just celebrated Christmas together and then went off to London for a holiday.

Today I thought I would share a gift with you.

Kathryn and I exchange books for the holiday. We do not wrap them—our tradition, which she started years ago. I like doing this. Ken’s family re-uses wrapping paper year-to-year. I am pleased to see that there is a call to save wrapping on three gifts.

If every American family wrapped just 3 presents in reused materials, it would save enough paper to cover 45,000 football fields.

Kathryn gave me a wonderful collection of books. One of them is not the book: Computers, Rigidity, and Moduli: The Large-Scale Fractal Geometry of Riemannian Moduli Space. The author is Shmuel Weinberger a mathematician from the University of Chicago. I already had his book but finally took a look at it while browsing my other gifts. So it is a delayed gift, from a Christmas past.

The book is a combination of computer results, basic math results, and advanced math results. The last are a variety of topics that are well outside of my zone. I did like the book. Weinberger is a terrific writer, a terrific explainer, a gifted selector of topics. I was surprised to see that his book contained a puzzle that I had not thought about before. The puzzle is, like all good puzzles, easy to state—but hard to solve. At least for me. I did not see how to solve it. I hope you like it.

A Puzzle

Imagine that there are {2n} distinct points in the plane. No three points are collinear. Half of them, {n} are labeled red and the other half are labelled green. Festive colors. Your job is to connect each red point with a unique green point by a straight line. That is easy, of course. But we hate when lines cross. So your job is more: Please select the lines so that the fewest ones cross.

Thus the problem is. Find the fewest line crossings possible. As usual we wish to know the answer as a function of {n}. Is it {\sqrt{n}}? Or {\log(n)}? What is the best possible in the worst case?

The artwork on the wall behind Kathryn suggests a possible arrangement, likewise the floor. The art object directly behind her is in 3D space which is not allowed—but this is a photograph so its points are projected onto a plane anyway. Again, it’s important that no three points are collinear.

There is a Best

For start we note that there is always a best. Each of {n} red points can match one of {n} green points. So there are only a finite number of possible matchings, namely

\displaystyle  n! = n \times (n-1) \times \cdots \times 1.

This shows that there is always a best answer; moreover, it can be found. But {n!} can be huge, so another part of the question is: Can you find the best answer fast? How about finding the best answer in polynomial time?

A Solution

The best answer is that the number of crossings is always at most

\displaystyle  b(n) = c \log(n),

where {c} is the constant

\displaystyle  10^{2}+11^{2}+12^{2}- 13^{2} - 14^{2}.

Here is a proof that this bound is correct. Suppose that you have selected the fewest number of line crossings. We will argue that there are at most {b(n)} line crossings. The plan is to show that we can descend—that is given a matching we can try and decrease the number of lines that cross.

Given any two red nodes and any two green nodes, we can define the operation swap by having them exchange partners. If their lines cross before the swap, then after the swap the lines will not cross. The following figure shows this:

Oops. I thought the idea was to define an operation so that the number of line crossing could always be decreased. Wait the argument does not work. In the above figure the switch increases the number of crossings.

There is a saving trick, however. Do not attempt to decrease the number of lines that cross. Instead decrease the total length of the lines selected. The above figure can be turned into a proof of a lemma that a swap of two crossing lines always decreases the sum of their lengths. The cool idea is that the swaps may actually increase the number of crossings, but they will always decrease the total length.

In the end the length is minimal and there are {0} crossings. Thus

\displaystyle  b(n) = 0.

I cheated and used that

\displaystyle  10^{2}+11^{2}+12^{2} = 13^{2} + 14^{2},

and so the constant {c} is zero. Finally, no swap is ever undone—since the length always decreases—and so the process must finish within {O(n^2)} swaps.

Open Problems

Hope that you liked this puzzle. I think it shows that are sometimes methods that while simple may be hard to find. Is {O(n^2)} really the needed number of swaps? Are more than a linear number of swaps ever required?
Happy holidays to all.

3 Comments leave one →
  1. December 27, 2019 12:55 pm

    Is this in anyway related to the “stable marriage problem”?

  2. December 28, 2019 4:49 pm

    FYI, this is problem A-4 from the 1979 Putnam Exam.

  3. Cristóbal Camarero permalink
    January 15, 2020 12:30 pm

    Hello there. For some things I apply edge swaps in graphs, but I never have a clear measure to decrease. Does the book give results related to the puzzle? If so, I would probably should ask my University’s library to get it.

Leave a Reply to Cristóbal Camarero Cancel reply

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

You are commenting using your 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