The beginnings

The Beginnings Jos´e Luis A. Yebra (invited speaker) Universitat Politcnica de Catalunya Castelldefels Abstract The simple title tells many things. Of course, it could tell almost nothing since a well-known motto says that ‘everything must have a beginning’. However, another motto is more appropriate here: ‘A journey of a thousand miles must begin with a single step’. Yes, we remember here the first steps of a journey of more than 60/2 years; steps that set the basis for the first group of people working on Graph Theory not only at Barcelona, but in the whole of Spain. And all this began when Miguel Angel Fiol ... 1 Once ... in 1975-1979 I was going to say ”Once upon a time...” but I will be much more precise: I will speak of things that happened in the years 1975-79. This means more than 60/2 years ago. I am sure that some of you cannot remember this period and I see that some others were not yet among us. I think that to better understand the beginnings of the Graph Theory group at Barcelona we should travel back to those years. We need to become acquainted with the circumstances under which we worked; it is relevant to be conscious of the advantages but also the hardships of this period. It was during the 1975-79 years that the Vietnam War ended and the Iran revolution took place, while in Spain Franco died and for the first time in the last forty years we enjoyed democratic elections under a new Constitution. In Mathematics, it was the age of public-key cryptography and the RSA encryption algorithm, as well as the appearance of Mandelbrot 3 The Beginnings J. L. A. Yebra fractals. More generally the scientific world celebrated the appearance of the first personal computer, the first CD audio and the first human in vitro fertilization (which, incidentally, assures the older of us of our natural conception, perhaps one of the few advantages we have over the younger ones). Of course, there was no cellular phones, no DVD’s and no Internet. These few sentences compose a very fast review of the 1975-79 period and are not enough to understand the limitations encountered. So, I will come back to this issue. This flash-back is especially important for those under thirty years old, since they have not lived through this period. As the lyrics of La Boh`eme, the Charles Aznavour song goes: La boh`eme Very free translation Je vous parle d’un temps I tell you about a time que les moins de vingt ans That under-thirties ne peuvent pas connaˆıtre cannot know about Montmartre, en ce temps-l`a ... At that time, Miguel Angel ... At that time Miguel Angel was a young student of Telecommunication Engineering At the UPC and a columnist of the satirical journal “La codorniz”, surely unaware that new important activities were about to come. Its origin should be found in Martin Gardner’s column in Scientific American “Snarks, Boojums and other conjectures related to the four-color-map theorem” ([2]), together with the providential launch late in 1976 of “Investigaci`on y Ciencia”, the Spanish translation of the magazine, just in time to offer in the April 1977 issue the Snark’s article to a broad Spanish speaking audience that included Miguel Angel. But let us deviate a little from our theme to pay a small tribute to the immense figure of Martin Gardner, who has died just three weeks ago. He has been the most important writer in recreational mathematics. Surely all of us have enjoyed many of his writings. When we affirm that without him we would not be here, we can ask how many other mathematicians should also acknowledge an analogous origin. Thanks a million, Martin, for all the delightful moments you have given us and for the wonderful world you did open to us. 4 The Beginnings J. L. A. Yebra 2 From the 4-colour problem to Snarks In those years there was much research on the so-called 4-colour problem: Can every planar map be coloured using at most four colours in such a way that regions sharing a common boundary (other than a single point) get different colours? Fallacious proofs were given independently by Kempe (1879) and Tait (1880). Kempe’s proof was accepted until 1890 when Heawood showed an error. It is easy to proof that five colours suffice, but reducing the number of colours to four proved to be very difficult. On April 1, 1975, Martin Gardner published a map with the claim that it required five colours if adjacent countries were to receive distinct colours. Of course, the map could be 4-coloured: It was just an April 1 Fool’s joke. To any planar map (where at most three countries meet at any boundary point) can be associated a 3-regular planar graph with boundaries between countries seen as edges and reciprocally. And it is very easy to proof that such planar map can be 4-coloured if and only if the edges of its associated 3-regular graph can be properly 3-coloured. Here properly means that the three edges meeting at every vertex get different colours. As a consequence, it became interesting to find 3-regular graphs that could not be properly 3-coloured. And if any such graph is planar the 4-colour problem is (negatively) solved. The positive result was finally obtained by Appel and Haken (1977), who constructed a computer-assisted proof that four colours sufficed. Some mathematicians did not accept it. However, the proof appeared valid and the result is accepted today as the 4-colour theorem. A shorter proof has since been constructed by Robertson et al. in [4]. Martin Gardner’s proposed to use the term snarks for nontrivial 3regular graphs that are not 3-coloreable. The name comes from Lewis Carroll’s ‘The hunting of the Snark’ because of its elusive character. Just a few years before only a handful of snarks were known: The first one was the ubiquitous Petersen graph on 10 vertices, found in 1898; the next are two graphs on 18 vertices due to Blanusa (1946); the following one is a graph on 210 vertices found by B. Tutte, and the last one was a graph on 50 vertices found by G. Szekeres in 1973. Then Martin Gardner’s article presented the work of Rufus Isaacs who discovered two infinite families of snarks in 1975, see [3]. As other Martin Gardner articles, it fostered much research on the subject. Miguel Angel generalized some of Isaacs’s constructions by a quite new approach based on Boolean Algebra. 5 The Beginnings J. L. A. Yebra 3 Communicating with the scientific community Once the new constructions were ready, a new problem arose: What can man do with them? There was a simple answer: Communicate it to the scientific community. But remember that we were in 1977. There were no personal computers, nor any of those fancy things we can use with them. There was no such thing as e-mail. In those years communication meant to type a letter, to put it inside something called envelope, to stick in the front side a stamp, to put it in a mailbox and to wait several weeks for an answer. Perhaps I am exaggerating since every body knows what an envelope and a stamp are, but for how long? The most practical way of writing consisted in typing with a writing machine. We should remember that, since there were no personal computers, there was no such thing as word processors, style or Grammatik correctors, not even a delete key to correct the smallest errors, which were corrected by taking the sheet of paper out of the writing machine, creasing it (avoiding uttering four letter words) and beginning again with a new sheet. Besides, at school people learnt some French, but communicating with the scientific community meant to write in English. Therefore, you can understand that the first two letters that Miguel Angel addressed to Martin Gardner were written in Spanish, beginning with Barcelona, 6.XI.77 Barcelona, 22.XI.77 Sr. D. Martin Gardner Sr. D. Martin Gardner E.E.U.U. E.E.U.U. Apreciado Sr.: Apreciado Sr.: Soy estudiante ... Como continuaci´on ... Well I do not know what most of us would do when receiving letters written in an alien language and related to some relatively aged work. But we know what Martin Gardner and Rufus Isaacs did through the answer of the latter, dated December 21, 1977: Dear Sr. Fiol Martin Gardner has forwarded me your two letters. Both look very interesting. I regret the delay in replying, but this was mainly due to my unsuccessful efforts to find a Spanish translator. 6 The Beginnings J. L. A. Yebra By I think I understand you because of your beautiful drawings and because you are travelling a road I have been over myself. For example ... Very nice from R. Isaacs but, since he has understood only the drawings, he had missed most of Miguel Angel work. It was imperative to communicate in English. How? Well, look at the way Miguel Angel did it: First type the letter in Spanish, double spaced: Agradezco su carta del 21.XII.77, as´ı como tambi´en el folleto conteniendo su art´ıculo sobre los Snarks. Ambos los he le´ıdo con mucho inter´es ... Then look for someone that can translate it into English placing the handwritten translation between the Spanish lines, so as to obtain: Agradezco su carta del 21.XII.77, as´ı como tambi´en el folleto I want to thank you for your letter of December 21, 1977 as conteniendo su art´ıculo sobre los Snarks. Ambos los he le´ıdo well as your paper about the Snarks. I’ve read both of them con mucho inter´es ... carefully ... Finally, typeset the English version to achieve some thing like I want to thank you for your letter of December 21, 1977 as well as your paper about the Snarks. I’ve read both of them carefully ... 7 The Beginnings J. L. A. Yebra The final result is a long typeset English letter ... without errors! And remember: without even a delete key to correct a single error. But this effort pays: The answer from Rufus Isaacs says: Dear Senor Fiol, I owe you my deepest apologies on two grounds. First, ... Second, for under-estimating the depth of your work. I see now you have made contributions of insight and importance. Congratulations! I am enclosing a paper which I was arranging to publish in a graph theory journal. With your permission I should like to write a similar piece on your work. (...) I thing you should write a polished paper on your own about your fine Boolean logic method of generating snarks. (...) And in a letter dated November 29, 1978 Rufus Isaacs offers: I recently spoke to Professor Gore, telling him my high opinion of you. He seems interested in your joining the faculty... An offer to join the Johns Hopkins University that Miguel Angel could not accept because ... he was still a undergraduate student! 4Conclusion Under my light supervision Miguel Angel wrote his graduation thesis about the construction of snarks using Boolean operators. It is difficult to summarize here its more than two hundred pages. I will just restrict myself to showing below that the Petersen graph is a snark and refer to Miguel Angel’s paper [1] for the way Boolean logic enters the snarks’ world. The Boolean family contains the BDS family of Isaacs and some later additions by other authors as Loupekhine. But it also contains many more new snarks. 8 The Beginnings J. L. A. Yebra To see that the Petersen graph is a snark, notice that to properly colour the edges of a pentagon, any colour can be used at most twice. Thus, three colours are needed, using two of them twice and the other one just once. This is the only proper colouring of the pentagon except for permutation of the colours. As a consequence, the edges adjacent to those vertices (we will called them semi-edges) must be coloured as in figure . Notice that one colour appears three times in consecutive semi-edges while the other two colours appear just once in the remaining semi-edges. Again the colouring is unique except for permutations of the colours. When we draw the pentagon as the ‘inside’ pentagon in the usual representation of the Petersen graph this circular ordering is modified, so that the three semiedges equally colored are not consecutive, see Figure 1. As a consequence, the Petersen graph cannot be properly coloured. It is possible to colour at most three of the five edges joining the ‘inside’ and the ‘outside’ pentagons, see Figure 1, where the remaining two edges sholud be coloured 1 at one end and 3 at the other one.   L L L L   Z Z Z Z   P P  J J   L L L L   Z Z Z Z  P P  J J  L L L L L L   Z Z Z Z Z   L L L L   Z Z Z Z    PPP 1 2 3 21 3 23 31 3 23 31 3 23 31 1 3 Figure 1: The Petersen graph Today, thirty two years later, all small snarks are known. For instance, there are exactly 2 snarks on 18 vertices, 6 on 20 vertices, 20 on 22 vertices, 38 on 24 vertices, 280 on 26 vertices and 2900 on 28 vertices. We could also speak of Miguel Angel’s PhD Thesis (1981); we could speak of Minimal Connections, Double Loop Networks, Tessellations, Line Digraphs, the (Δ,D) problem, etc. But this will take us much longer. Today, Miguel Angel is more than sixty year old. This is a consequence of the simple addition rule. But the most important thing is that instead of being alone there are more than 60/2 other people working in Combinatorics and Graph Theory at Barcelona, not counting those people that 9 The Beginnings J. L. A. Yebra work at other places after been initiated here. References [1] M.A. Fiol. A Boolean algebra approach to the construction of snarks. Graph Theory, Comb. and Appl. Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk., Eds. New York: John Wiley & Sons, Vol.1, 493–524, 1991. [2] M. Gardner. Snarks, Boojums and other conjectures related to the four-colormap theorem. Scientific American, 234:126–130, 1976. [3] R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable. Amer. Math. Monthly, 82:221-239, 1975. [4] N. Robertson, D. Sanders, P. Seymour, and R. Thomas. The FourColour Theorem. J. Comb. Theory B, 70(1):2–44, 1997. 10