## Paul Erdős

The Hungarian mathematician Paul Erdős died in 1996. Soon afterwards, I wrote up a memoir of my recollections of working with him, which I revised ten years later. I have decided to post a slightly modified version here. For Paul was a great collaborator; indeed, the increasing amount of collaboration among mathematicians in the twentieth century matches well with his career, and I have no doubt that he played a very important role in this. I hope to say more about mathematical collaborations here, time permitting.

For more information about Erdős and the concept of “Erdős number” (the mathematician’s equivalent of “Bacon number”), see the Erdős number website maintained by Jerry Grossman.

My encounters with Paul Erdős were brief and occurred late in his life. Nevertheless, I have been enriched by this contact. Here is an attempt to describe it.

### Prologue: two train journeys

My memoirs of Paul Erdős will be almost all entirely personal, but I would like to begin with two small incidents illustrating attitudes of the mathematical community and the wider world to Paul. Both took place on trains.

After I received my copy of the two-volume work The Mathematics of Paul Erdős (published just after Paul’s death), I was reading it on the train home from work. Sitting opposite me was a non-mathematician, who noticed what I was reading. He was familiar with the concept of Erdős number and, after striking up a conversation, he raised this topic, and was delighted to learn that my Erdős number was 1.

A rather different reaction came from an eminent mathematician whom I met by chance on a train in Europe. He was sceptical about Paul Erdős and his mathematics, and was reluctant to believe that someone like, for example, Jean-Pierre Serre could have an Erdős number. On the spot, I was able to construct a path of length 5 from Erdős to Serre passing through me. I learned later that Serre has Erdős number 3; but my pride was restored when I read that Efim Zelmanov had Erdős number 4 and the shortest path passed through me. (But even this is no longer true. So short-lived is fame . . .)

### New Cross and Cambridge

I began my mathematical life as a group theorist. I heard Paul Erdős speak on several occasions, but somehow I never managed to connect his mathematical interests with mine.

Bélà Bollobás organised two conferences in Cambridge for Paul Erdős which I attended, for his 70th birthday in 1983 and for his 75th in 1988. By the first, I had been working on something which Paul had invented but not exploited, the unique countable random graph. I hoped he would enjoy hearing about the richness of this wonderful object. But, sad to say, I was scheduled to speak on the last morning of the conference, and by then Paul had already left. I subsequently wrote the paper I should have written then, which was published in The Mathematics of Paul Erdős.

By 1988, our relationship was entirely different as a result of what had occurred less than a year earlier, at the British Combinatorial Conference at Goldsmiths College. Paul and I were among the invited speakers. I talked about sum-free sets, a topic which had arisen indirectly from my work on highly symmetric graphs resembling the random graph (specifically, Henson’s triangle-free graph: I presented it as an infinite analogue of the 100-vertex Higman–Sims graph, about which I had spoken at my previous BCC talk, at the other end of London in 1977.)

This was a topic which caught Paul’s interest, not as group theory or graph theory but combinatorial number theory. He had thought about sequences of natural numbers satisfying various conditions, for example, Sidon sets (containing no solution of x+y=z+w), and sets containing no 3-term arithmetic progressions. Usually the main question is the extremal problem: What is the largest size of such a set in [1,n]?

For my purpose I needed to measure the collection of all sum-free sets in various ways, of which counting them is the simplest. The question, How many sum-free subsets of [1,n], caught Paul’s interest.

As a result, we communicated about this and related questions. Paul immediately saw that the counting question could be extended to other classes, and was related to the maximum size question. If a family of subsets of [1,n] is closed under taking subsets, and the largest set in the family has k elements, then the number of sets lies between (roughly) 2k and nk. Moreover, a family whose size is close to the lower bound will have just a few sets of maximum size which probably determine its structure, whereas one close to the upper bound will be more uniformly spread out.

At his birthday conference in Cambridge, Paul stayed in the Judge’s Room, the largest guest room in Trinity. Every morning, a full English breakfast was delivered to his room at 7 o’clock. Of course, this was far more than he needed to eat, so I was instructed to come to his room at that time to help him eat it (and to work on counting the sum-free sets).

It is easily seen that a sum-free subset of [1,n] has size at most n/2 (rounded up). This bound is attained in two quite different ways: by the set of odd numbers, or by the set of all numbers greater than n/2 (or a slight variant). Our conjecture was that the number of sum-free sets is around c2n/2, and that most of these sets are either sets of odd numbers or sets of numbers greater than n/2-w(n), where w(n) is a slowly-growing function. (More precisely, there should be two different values of the constant c, depending on the parity of n. The reason for this piece of pedantry can be seen by considering sets of odd numbers: there are 2n/2 of these if n is even, or 2(n+1)/2 if n is odd.)

We were unable to prove this, but after an epic struggle we could show that the number of sum-free sets with all elements greater than n/3 obeys such a law. Our conjecture is equivalent to the assertion that almost all sum-free sets are either of this type or sets of odd numbers.

The conjecture is still open, although apparently more general conjectures have been settled subsequently. To the best of my knowledge, Paul never offered money for it, though he mentioned it occasionally in talks.

We also looked at restrictions other than sum-freeness. The second part of our paper gives a collection of results and conjectures on the numbers of such sets, closely related to earlier work (much of it Paul’s) on the largest size of such a set. It was for me a crash course in combinatorial number theory, as Paul drew my attention to classics such as his Tomsk paper in which he first used graph-theoretic methods in number theory, and the occasion where he was pre-empted by Kalmár.

The other result of these breakfast sessions was that I grew to know and love Paul. He would break off from mathematics, without taking a breath, to tell an anecdote, discuss Australian politics, or whatever. His views were so open, human, and liberal that I fell entirely under his spell.

My talk at the meeting was on random permutations, another Erdősian subject. However, this elicited no response from him. I will discuss it later.

The following year, I saw him again in Cambridge, at Reinhard Diestel’s conference on infinite combinatorics. A collaboration has its rhythm, and ours was no longer in the white-hot phase. What talk we had there was of other things. I had just visited Little Gidding, the site of Nicholas Ferrar’s community in the seventeenth century which was the inspiration and subject of the fourth of T. S. Eliot’s Four Quartets. Ferrar had tried to isolate his community from the world of politics, but the interest King Charles had shown in the venture brought trouble from the Puritans in the Civil War. Paul was of course more interested in the political fallout than in the religious vision or its literary consequence. (The story of Little Gidding is told here.)

But I felt I had been invited to join a very important club when Paul asked me to write up our results and send them to Richard Mollin for the proceedings of a Canadian Number Theory Association meeting in Banff. As a result of my unpardonable ignorance of Canadian mathematicians (and perhaps, in part, of Paul’s accent), I sent it first by mistake to Ron Mullin.

### Interlude: Hakone

In 1990, before the ICM in Kyoto, I attended the Second Japanese Graph Theory Conference in Hakone.

Apart from the fact that my only photos of Paul were taken on the conference excursion (my favourite is of him paddling in the lake), this meeting was important for me for many reasons. One, related to this story, was a collaboration with Laci Babai, inspired by a question of Misha Klin. Laci and I have collaborated on several occasions, but have not always been good at publishing the results. Indeed, the work we did on this occasion has never appeared: the theorem we thought we proved contained a mistake; Laci thinks he can fix it, but I, less of a perfectionist, am satisfied with a weaker result. But maybe one day . . . (An even older paper of ours from the early 1980s was published in 2000; it comes into the story later on.)

### Mátraháza and Wimbledon

In autumn 1995, a workshop on combinatorics was held in the rest house of the Hungarian Academy of Sciences at Mátraháza, in the mountains about an hour’s drive from Budapest.

I arrived at the airport on a plane from London. Before I had time to look for a bus to the city, I saw Paul waiting for me in the arrivals lounge. He had arranged for an Academy car and driver to take him out to the airport to meet me. He had also made all the other arrangements for my stay: I slept in “his room” in the Academy guesthouse on the Castle Hill; he took me to his favourite restaurant; and he arranged another car and driver to take us to Mátraháza the next day. I will never forget his openness and generosity to me on this occasion; he was welcoming me to his native land, and though I was a very ordinary workshop participant he made me feel very greatly honoured.

At Mátraháza, it once again turned out that Paul was not much interested in my talk, but he had many new ideas about our earlier collaboration, which we discussed while sitting in the comfortable chairs at the rest house or strolling around the grounds.

From the comments earlier, it is clear that good upper bounds for the number of maximal sum-free sets could settle our conjecture, so we looked at these in more detail, along with maximal sets subject to the other constraints we had looked at in Cambridge. Also, our work had shown the importance of the least element in a sum-free set, and we looked at the curious function giving the maximum size of a sum-free set with given least element.

In the summer of 1996, Paul came to London. He stayed with a Hungarian lady who lived in a very fine house on the slope of a hill in Wimbledon. After his seminar at Imperial College, and also after he had visited me to work, I was invited (or summoned) to her house to continue the mixture of work and talk which collaboration with Paul Erdős always involved.

During one of these visits, an unforgettable experience occurred. The house lights were turned off, the floodlights in the large sloping garden were switched on, and two foxes came to play in the light. Their coats shone as they danced a formal ballet in the garden and we watched spellbound.

By the time he left, Paul thought we had enough for a second paper, which should be submitted to the workshop proceedings (to which I had also sent the paper of my talk).

### Epilogue: Montréal and Budapest

Later in 1996, I attended a workshop on symmetric graphs in Montréal. On the day after the workshop, Laci Babai (who had a computer account there) and I agreed to try to make the final revisions to our long-delayed paper on switching classes of tournaments, which was begun in the early 1980s. I fetched the file from London by FTP and we each set to editing parts of it.

I finished my work before Laci did, and decided to read my mail. Doing this by telnet across the Atlantic in those days was a slow business, but eventually, up on the screen came a message reporting the death of Paul Erdős. I sat there stunned, and was unable to say anything to Laci for some time. When I did, we both sat there stunned.

When the revisions were finally complete (a few years later), we dedicated the paper to Paul Erdős. The dedication reflected not only that poignant moment during its creation, but also the fact that we used the probabilistic method in a novel way, to construct objects with prescribed automorphism groups. The paper was published in the Electronic Journal of Combinatorics.

The paper based on our work at Mátraháza was accepted for publication in the workshop proceedings, and appeared in the journal Combinatorics, Probability and Computing.

In 1999, a large international conference was organised in Budapest in Paul’s memory. I was honoured with an invitation to speak. Though my work with Paul had all been in the area of combinatorial number theory, the organisers (reasonably) labelled me as an algebraist. I decided to survey another area associated with Erdős.

In the 1950s and 1960s, Erdős and Turán had written a series of papers with the title “On some problems of a statistical group theory”. This was mainly devoted to deriving subtle properties of the distribution of cycle lengths in a random permutation in the symmetric group on n symbols.

I contend that there is more to statistical group theory than this: group theory is concerned with structure, with subgroups rather than elements. I feel that Dixon’s theorem, which asserts that two random permutations generate the symmetric or alternating group with high probability, is a better pointer to the future of “statistical group theory”. Though Paul often posed group-theoretic problems to me, this was not a subject in which his insights would light the way for others. (This is borne out by the Budapest conference, where algebra was the smallest section, with only five speakers, four of whom took the papers of Erdős and Turán as their starting point. Péter Pál Pálfy, or P3, was the honorable exception.)

Questions of the type Erdős considered in other areas, for example extremal problems, can also be posed for permutations. (Strangely, Paul did not seem to have worked on this area himself: the nearest I can find in his bibliography is this paper.) The paper I wrote for the conference attempts to survey this area and to indicate the influence (both direct and indirect) of Erdős. Nevertheless, I don’t think Paul would have come to my talk had he been there, and even if he had, I don’t think I would have got much response from him.

The conference itself was an outstanding success. Two things let it down, in my view. First, so many outstanding mathematicians accepted the invitation to talk that very often I found myself wanting to go to all the parallel sessions in a time slot. (Indeed, I would happily have skipped my own talk to go to hear somebody else; I was competing with Eduard Wirsing, Endre Szemerédi, Jarik Nešetřil, and Walter Hayman!) The conference was the victim of its own success.

But it also showed signs of a developing “Erdős industry” which in my opinion is not wholly to the good. Paul Erdős’ influence on mathematics depended on his knowledge of and feeling for, both the difficulty of his problems, and the strengths and abilities of his collaborators; he always treated us as individuals. He is quite irreplaceable, but we should keep this in mind when we honour his memory.

#### Bibliography

1. L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments
, Electronic J. Combinatorics 7(1) (2000), article #R38.

2. P. J. Cameron, The random graph,
pp. 331–351 in The Mathematics of Paul Erdős, (ed. R. L. Graham and J. Nešetřil), Springer, Berlin, 1996.

3. P. J. Cameron, Permutations,
Proceedings of Paul Erdős memorial conference.

4. P. J. Cameron and P. Erdős, On the number of sets of integers with various properties,
pp.61–79 in Number Theory (ed. R. A. Mollin), Walter de Gruyter, Berlin, 1990.

5. P. J. Cameron and P. Erdős, Notes on sum-free and related sets,
Combinatorics, Probability and Computing 8 (1999), 95–107.

6. J. D. Dixon, The probability of generating the symmetric group,
Math. Z. 110 (1969), 199–205.

7. T. S. Eliot, Four Quartets, Faber, London 1944.

8. P. Erdős, On sequences of integers no one of which divides the product of two others and on some related problems,
Mitteil. Forsch.-Inst. Math. Mech. Univ. Tomsk 2 (1938), 74–82.

9. P. Erdős, N. Linial and S. Moran, Extremal problems on permutations under cyclic equivalence,
Discrete Math. 64 (1987), 1–11.

10. P. Erdős and A. Rényi, Asymmetric graphs,

Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.

11. P. Erdős and P. Turán, On some problems of a statistical group theory,
I, Z. Wahrscheinlichkeitstheorie und Verw. Gebeite 4 (1965), 175–186; II, Acta Math. Acad. Sci. Hungar. 18 (1967), 151&nash;164; III, ibid. 18 (1967), 309–320; IV, ibid. 19 (1968), 413–435; V, Period. Math. Hungar. 1 (1971), 5–13; VI, J. Indian Math. Soc. (N.S.) 34 (1971), 175–192; VII, Period. Math. Hungar. 2 (1972), 149–163.

12. R. L. Graham and J. Nešetřil (eds.), The Mathematics of Paul Erdős,
Springer, Berlin, 1996.

13. L. Kalmár, Über das Problem der “Factorisatio numerorum”,
(Hungarian) Mat. Fiz. Lapok 38 (1931), 1–15.

14. R. Van der Weyer, Little Gidding: Story and Guide
, Lamp Press, London, 1989.

#### Update, August 2006

A few things more can be said now.

1. The proceedings of the Erdős memorial conference have appeared: Paul Erdős and his Mathematics, (ed. G. Halász, L. Lovász, M. Simonovits and V. T. Sós), Bolyai Society Mathematical Studies, Springer, Berlin, 2002. My paper on “Permutations” is in Volume 2, pp.205–239.
2. It is now much easier to find Erdős numbers: MathSciNet has a web page which gives this information directly (though you have to be a subscriber to use it). So I find that Serre’s Erdős number is 2 (the common co-author is Sarvadaman Chowla), and Zelmanov’s is 3. However, it should be said that this is not the “official Erdős number” as maintained by Jerry Grossman, since MathSciNet recognises editing a conference proceedings or writing an obituary as a joint publication whereas Grossman insists on a piece of research mathematics.
3. Most significantly, the “Cameron–Erdős conjecture” on the number of sum-free sets has been proved by Ben Green in his Cambridge PhD thesis, published as B. Green, The Cameron–Erdős conjecture, Bull. London Math. Soc. 36 (2004), 769–778. An independent proof was found by Sasha Sapozhenko.
4. And Laci Babai and I never did get around to finishing that paper!