Solving a problem posed by Paul Erdös

Prof Herbert Fleishner

In the last issue of Zimaths, personal encounters with Paul Erdos were described by `one of the lucky many' who had the chance to meet `Uncle Paul' on various occasions. This time the same person wants to report on how he and one other chap solved one of Erdös' problems. And like many of Erdös' problems it had a prize attached to it --- US$100. A prize which --- for the problem solvers -- would mean more than ten free tickets to the Olympics. For the money came by a check signed by Paul; and once the check was cashed it would be sent back to the solver(s) upon request. Almost like a ritual, many recipients of such checks would then frame it and hang it up on the wall of their office like a certificate.

Once upon a time (1990, actually) there was a conference in Hindsgavl in Denmark, quite close to the birthplace of the poet Hans Christian Andersen. The conference was not on children's stories however, but on graph theory and combinatorics. I had the honour to chair Uncle Paul's and the subsequent problem seminar --- and I have the videotape to prove it! The first problem Erdös spoke about was this, albeit in a different phrasing:

Suppose you are given an n x n matrix where entries are integers such that no integer appears more than once in the same row and any two rows have at most one element in common. Prove that one can rearrange the entries in each row in such a way that equal entries always appear in the same column. The prize attached to that problem was and still is US$500. Try it before you go to bed. Hopefully it won't create nightmares for you. For me it did, since I had started working on that problem in 1975; at that time its prize was US$50. The tenfold multiplication of the problem's worth ``was not entirely due to inflation,'' Erdös assured us. So at least I had contributed something to his problems so far --- I had shown by my futile attempts that this problem was really hard.

The next problem he stated was the Cycle-Plus-Triangles Problem: Suppose you are given a regular 3n-gon (eg for n=2, we would have a hexagon) C in the plane and n triangles whose sides are diagonals of C such that every vertex of C belongs to exactly one of these n triangles. Show that the vertices of C can be coloured with three colours such that no two vertices of the same colour are adjacent in C (ie, are joined by an edge of C), nor do they belong to the same triangle. The prize attached to this problem: US$100.

Over a year later, I was invited to spend two weeks at the Technical University in Ilmenau, Germany, just to have a good time with my colleagues -- mathematically. There was also my younger colleague Michael Stiebitz. He had had the nerve to fiddle around with this US$100 problem, and dared to invite me (the burned child --- see above) to discuss it seriously. ``Poor soul,'' I thought, ``If you think I'll ever try again to seriously tackle an Erdös problem, you are badly mistaken.'' But I couldn't resist joining him in fiddling around.

He had come up with some preliminary results (some of which contained easily correctible flaws) and a yet-to-be-proved theorem which, if true, would imply the validity of Erdos' conjecture. But how to prove it? He gave a few suggestions. ``Sounds nice'' I thought, but what then? In any case, I didn't take his ideas too seriously, not because they seemed inappropriate, but because of yet unknown complications and difficulties, which I believed to be in store for us.

I had arrived in Ilmenau on Sunday evening; by 1am on Thursday I had a counterexample to Erdös' conjecture. However, by 8.30am the next (correction, same!) morning, while waiting for Michael in the Department so I could show him the counterexample, it turned out, upon checking it again, that I had erred --- it was not a counterexample. All I had proved was that brain cells of certain people work with a varying degree of accuracy depending on the time of day.

By 10.00 am, Michael had arrived and we went to a classroom to summarize what we'd got so far and discuss what to do next. I gave some methods. He gave his. Then we found some equations. Then we slogged on --- till we ended up with a sum of six integral terms which could be grouped into three pairs of equal numbers, ie we had a sum of the form 2(a₁+a₂+a₃). We stared at it. ``What shall we do with it?'' we asked ourselves.

I had the idea to go back to the sum of six terms and write each term as a sum of two smaller terms (which we succeeded in doing in a very appropriate way --- whatever `appropriate' may mean in this context) and ended up with a sum of twelve terms. Using the equations we had found before, we were able to group these terms into three quadruples of equal numbers; ie we had a sum of the form 4(b₁+b₂+b₃). ``We have proved it!'' Michael exclaimed. I stared at him without really knowing what we had proved. It took him a few minutes to make me see why our result proved his theorem, and thus Paul's conjecture. He was overjoyed --- I wasn't.

``Listen, my young friend, you don't prove a conjecture by Paul Erdös within a few hours (by that time it was approximately 4pm). ``And we did it!'' ``I don't believe it --- let's go to the beginning!'' We did; no mistake found. However, I insisted that there must be a flaw somewhere. He refuted my suspicions. In order not to quarrel too much over a possibly false proof, I offered a compromise: ``Let's have dinner, then we come back, erase everything that's on the blackboard, and let's start from scratch.'' He agreed. Said, done and it was 10pm and I was still not convinced. Another compromise: ``Let's have a coffee, and then we go through it again. If we don't find a mistake, then I'll believe it'', I said.

We went to the Secretary's office, where he made the coffee for me. I sipped my coffee, taking my time and wiggling my head in disbelief, I finished the cup and put it on the tray. ``Let's go back to the classroom and do it again'' I said. ``If you want to, go there alone'', he replied ``I'm going home 'cause I'm tired.'' I refused to disillusion myself without his presence. We both left, he accompanied me to my room on campus, and about 30 minutes later I had fallen asleep, still having doubts about the correctness of our proof.

But we never got to discuss it, for he had to go to see his mother in Berlin over the weekend, and then proceed to Denmark. Instead he left a handwritten draft of our joint proof (which was absolutely correct, despite my doubts) waiting in the Secretary's office for me when I arrived at 9am on Friday. I spent the second week of my stay without him, enjoying a relaxed atmosphere with other colleagues.

A few months later we received our cheques (US$50 for each of us), after the paper got accepted for publication, and I did what others did with their cheques --- cashed it and framed it.