The Beginnings
Jos´e Luis A. Yeb a (in i ed speake )
Uni e si a Poli cnica de Ca alunya
Cas ellde els
Abs ac
The simple i le ells many hings. O cou se, i could ell almos
no hing since a well-known mo o says ha ‘e e y hing mus
ha e a beginning’. Howe e , ano he mo o is mo e app op ia e
he e: ‘A jou ney o a housand miles mus begin wi h a single
s ep’. Yes, we emembe he e he fi s s eps o a jou ney o mo e
han 60/2 yea s; s eps ha se he basis o he fi s g oup o
people wo king on G aph Theo y no only a Ba celona, bu in
he whole o Spain. And all his began when Miguel Angel Fiol
...
1 Once ... in 1975-1979
I was going o say ”Once upon a ime...” bu I will be much mo e p ecise: I
will speak o hings ha happened in he yea s 1975-79. This means mo e
han 60/2 yea s ago. I am su e ha some o you canno emembe his
pe iod and I see ha some o he s we e no ye among us. I hink ha o
be e unde s and he beginnings o he G aph Theo y g oup a Ba celona
we should a el back o hose yea s. We need o become acquain ed wi h
he ci cums ances unde which we wo ked; i is ele an o be conscious o
he ad an ages bu also he ha dships o his pe iod.
I was du ing he 1975-79 yea s ha he Vie nam Wa ended and he
I an e olu ion ook place, while in Spain F anco died and o he fi s
ime in he las o y yea s we enjoyed democ a ic elec ions unde a new
Cons i u ion. In Ma hema ics, i was he age o public-key c yp og aphy
and he RSA enc yp ion algo i hm, as well as he appea ance o Mandelb o
3
The Beginnings J. L. A. Yeb a
ac als. Mo e gene ally he scien ific wo ld celeb a ed he appea ance o
he fi s pe sonal compu e , he fi s CD audio and he fi s human in
i o e iliza ion (which, inciden ally, assu es he olde o us o ou na u al
concep ion, pe haps one o he ew ad an ages we ha e o e he younge
ones). O cou se, he e was no cellula phones, no DVD’s and no In e ne .
These ew sen ences compose a e y as e iew o he 1975-79 pe iod and
a e no enough o unde s and he limi a ions encoun e ed. So, I will come
back o his issue.
This flash-back is especially impo an o hose unde hi y yea s old,
since hey ha e no li ed h ough his pe iod. As he ly ics o La Boh`eme,
he Cha les Azna ou song goes:
La boh`eme Ve y ee ansla ion
Je ous pa le d’un emps I ell you abou a ime
que les moins de ing ans Tha unde - hi ies
ne peu en pas connaˆı e canno know abou
Mon ma e, en ce emps-l`a ... A ha ime, Miguel Angel ...
A ha ime Miguel Angel was a young s uden o Telecommunica ion
Enginee ing A he UPC and a columnis o he sa i ical jou nal “La codo -
niz”, su ely unawa e ha new impo an ac i i ies we e abou o come. I s
o igin should be ound in Ma in Ga dne ’s column in Scien ific Ame i-
can “Sna ks, Boojums and o he conjec u es ela ed o he ou -colo -map
heo em” ([2]), oge he wi h he p o iden ial launch la e in 1976 o “In es-
igaci`on y Ciencia”, he Spanish ansla ion o he magazine, jus in ime o
offe in he Ap il 1977 issue he Sna k’s a icle o a b oad Spanish speaking
audience ha included Miguel Angel.
Bu le us de ia e a li le om ou heme o pay a small ibu e o he
immense figu e o Ma in Ga dne , who has died jus h ee weeks ago. He
has been he mos impo an w i e in ec ea ional ma hema ics. Su ely all
o us ha e enjoyed many o his w i ings. When we affi m ha wi hou him
we would no be he e, we can ask how many o he ma hema icians should
also acknowledge an analogous o igin. Thanks a million, Ma in, o all he
deligh ul momen s you ha e gi en us and o he wonde ul wo ld you did
open o us.
4
The Beginnings J. L. A. Yeb a
2 F om he 4-colou p oblem o Sna ks
In hose yea s he e was much esea ch on he so-called 4-colou p oblem:
Can e e y plana map be colou ed using a mos ou colou s in such a way
ha egions sha ing a common bounda y (o he han a single poin ) ge
diffe en colou s? Fallacious p oo s we e gi en independen ly by Kempe
(1879) and Tai (1880). Kempe’s p oo was accep ed un il 1890 when Hea-
wood showed an e o . I is easy o p oo ha fi e colou s suffice, bu
educing he numbe o colou s o ou p o ed o be e y difficul . On
Ap il 1, 1975, Ma in Ga dne published a map wi h he claim ha i e-
qui ed fi e colou s i adjacen coun ies we e o ecei e dis inc colou s. O
cou se, he map could be 4-colou ed: I was jus an Ap il 1 Fool’s joke.
To any plana map (whe e a mos h ee coun ies mee a any bounda y
poin ) can be associa ed a 3- egula plana g aph wi h bounda ies be ween
coun ies seen as edges and ecip ocally. And i is e y easy o p oo ha
such plana map can be 4-colou ed i and only i he edges o i s associa ed
3- egula g aph can be p ope ly 3-colou ed. He e p ope ly means ha he
h ee edges mee ing a e e y e ex ge diffe en colou s. As a consequence,
i became in e es ing o find 3- egula g aphs ha could no be p ope ly
3-colou ed. And i any such g aph is plana he 4-colou p oblem is (nega-
i ely) sol ed. The posi i e esul was finally ob ained by Appel and Haken
(1977), who cons uc ed a compu e -assis ed p oo ha ou colou s su -
ficed. Some ma hema icians did no accep i . Howe e , he p oo appea ed
alid and he esul is accep ed oday as he 4-colou heo em. A sho e
p oo has since been cons uc ed by Robe son e al. in [4].
Ma in Ga dne ’s p oposed o use he e m sna ks o non i ial 3-
egula g aphs ha a e no 3-colo eable. The name comes om Lewis
Ca oll’s ‘The hun ing o he Sna k’ because o i s elusi e cha ac e . Jus
a ew yea s be o e only a hand ul o sna ks we e known: The fi s one was
he ubiqui ous Pe e sen g aph on 10 e ices, ound in 1898; he nex a e
wo g aphs on 18 e ices due o Blanusa (1946); he ollowing one is a
g aph on 210 e ices ound by B. Tu e, and he las one was a g aph on
50 e ices ound by G. Szeke es in 1973. Then Ma in Ga dne ’s a icle
p esen ed he wo k o Ru us Isaacs who disco e ed wo infini e amilies o
sna ks in 1975, see [3].
As o he Ma in Ga dne a icles, i os e ed much esea ch on he
subjec . Miguel Angel gene alized some o Isaacs’s cons uc ions by a qui e
new app oach based on Boolean Algeb a.
5
The Beginnings J. L. A. Yeb a
3 Communica ing wi h he scien ific communi y
Once he new cons uc ions we e eady, a new p oblem a ose: Wha can
man do wi h hem? The e was a simple answe : Communica e i o he
scien ific communi y. Bu emembe ha we we e in 1977. The e we e no
pe sonal compu e s, no any o hose ancy hings we can use wi h hem.
The e was no such hing as e-mail. In hose yea s communica ion mean
o ype a le e , o pu i inside some hing called en elope, o s ick in he
on side a s amp, o pu i in a mailbox and o wai se e al weeks o
an answe . Pe haps I am exagge a ing since e e y body knows wha an
en elope and a s amp a e, bu o how long? The mos p ac ical way o
w i ing consis ed in yping wi h a w i ing machine. We should emembe
ha , since he e we e no pe sonal compu e s, he e was no such hing as
wo d p ocesso s, s yle o G amma ik co ec o s, no e en a dele e key o
co ec he smalles e o s, which we e co ec ed by aking he shee o
pape ou o he w i ing machine, c easing i (a oiding u e ing ou le e
wo ds) and beginning again wi h a new shee .
Besides, a school people lea n some F ench, bu communica ing wi h
he scien ific communi y mean o w i e in English. The e o e, you can
unde s and ha he fi s wo le e s ha Miguel Angel add essed o Ma in
Ga dne we e w i en in Spanish, beginning wi h
Ba celona, 6.XI.77 Ba celona, 22.XI.77
S . D. Ma in Ga dne S . D. Ma in Ga dne
E.E.U.U. E.E.U.U.
Ap eciado S .: Ap eciado S .:
Soy es udian e ... Como con inuaci´on ...
Well I do no know wha mos o us would do when ecei ing le e s
w i en in an alien language and ela ed o some ela i ely aged wo k. Bu
we know wha Ma in Ga dne and Ru us Isaacs did h ough he answe
o he la e , da ed Decembe 21, 1977:
Dea S . Fiol
Ma in Ga dne has o wa ded me you wo le e s.
Bo h look e y in e es ing. I eg e he delay in e-
plying, bu his was mainly due o my unsuccess ul
effo s o find a Spanish ansla o .
6
The Beginnings J. L. A. Yeb a
By I hink I unde s and you because o you beau i ul
d awings and because you a e a elling a oad I ha e
been o e mysel . Fo example ...
Ve y nice om R. Isaacs bu , since he has unde s ood only he d awings,
he had missed mos o Miguel Angel wo k. I was impe a i e o commu-
nica e in English. How? Well, look a he way Miguel Angel did i : Fi s
ype he le e in Spanish, double spaced:
Ag adezco su ca a del 21.XII.77, as´ı como ambi´en
el olle o
con eniendo su a ´ıculo sob e los Sna ks. Ambos los
he le´ıdo
con mucho in e ´es ...
Then look o someone ha can ansla e i in o English placing he
handw i en ansla ion be ween he Spanish lines, so as o ob ain:
Ag adezco su ca a del 21.XII.77, as´ı como ambi´en
el olle o
I wan o hank you o you le e o Decembe 21,
1977 as
con eniendo su a ´ıculo sob e los Sna ks. Ambos los
he le´ıdo
well as you pape abou he Sna ks. I’ e ead bo h
o hem
con mucho in e ´es ...
ca e ully ...
Finally, ypese he English e sion o achie e some hing like
I wan o hank you o you le e o Decembe 21,
1977 as
well as you pape abou he Sna ks. I’ e ead bo h
o hem
ca e ully ...
7

The Beginnings J. L. A. Yeb a
The final esul is a long ypese English le e ... wi hou e o s! And
emembe : wi hou e en a dele e key o co ec a single e o .
Bu his effo pays: The answe om Ru us Isaacs says:
Dea Seno Fiol,
I owe you my deepes apologies on wo g ounds.
Fi s , ...
Second, o unde -es ima ing he dep h o you wo k.
I see now you ha e made con ibu ions o insigh and
impo ance. Cong a ula ions!
I am enclosing a pape which I was a anging o pub-
lish in a g aph heo y jou nal. Wi h you pe mission
I should like o w i e a simila piece on you wo k.
(...)
I hing you should w i e a polished pape on you own
abou you fine Boolean logic me hod o gene a ing
sna ks.
(...)
And in a le e da ed No embe 29, 1978 Ru us Isaacs offe s:
I ecen ly spoke o P o esso Go e, elling him my
high opinion o you. He seems in e es ed in you join-
ing he acul y...
An offe o join he Johns Hopkins Uni e si y ha Miguel Angel could
no accep because ... he was s ill a unde g adua e s uden !
4Conclusion
Unde my ligh supe ision Miguel Angel w o e his g adua ion hesis abou
he cons uc ion o sna ks using Boolean ope a o s. I is difficul o sum-
ma ize he e i s mo e han wo hund ed pages. I will jus es ic mysel
o showing below ha he Pe e sen g aph is a sna k and e e o Miguel
Angel’s pape [1] o he way Boolean logic en e s he sna ks’ wo ld. The
Boolean amily con ains he BDS amily o Isaacs and some la e addi-
ions by o he au ho s as Loupekhine. Bu i also con ains many mo e new
sna ks.
8
The Beginnings J. L. A. Yeb a
To see ha he Pe e sen g aph is a sna k, no ice ha o p ope ly colou
he edges o a pen agon, any colou can be used a mos wice. Thus, h ee
colou s a e needed, using wo o hem wice and he o he one jus once.
This is he only p ope colou ing o he pen agon excep o pe mu a ion
o he colou s. As a consequence, he edges adjacen o hose e ices
(we will called hem semi-edges) mus be colou ed as in figu e . No ice
ha one colou appea s h ee imes in consecu i e semi-edges while he
o he wo colou s appea jus once in he emaining semi-edges. Again he
colou ing is unique excep o pe mu a ions o he colou s. When we d aw
he pen agon as he ‘inside’ pen agon in he usual ep esen a ion o he
Pe e sen g aph his ci cula o de ing is modified, so ha he h ee semi-
edges equally colo ed a e no consecu i e, see Figu e 1. As a consequence,
he Pe e sen g aph canno be p ope ly colou ed. I is possible o colou a
mos h ee o he fi e edges joining he ‘inside’ and he ‘ou side’ pen agons,
see Figu e 1, whe e he emaining wo edges sholud be colou ed 1 a one
end and 3 a he o he 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
Figu e 1: The Pe e sen g aph
Today, hi y wo yea s la e , all small sna ks a e known. Fo ins ance,
he e a e exac ly 2 sna ks on 18 e ices, 6 on 20 e ices, 20 on 22 e ices,
38 on 24 e ices, 280 on 26 e ices and 2900 on 28 e ices.
We could also speak o Miguel Angel’s PhD Thesis (1981); we could
speak o Minimal Connec ions, Double Loop Ne wo ks, Tessella ions, Line
Dig aphs, he (Δ,D) p oblem, e c. Bu his will ake us much longe .
Today, Miguel Angel is mo e han six y yea old. This is a consequence
o he simple addi ion ule. Bu he mos impo an hing is ha ins ead
o being alone he e a e mo e han 60/2 o he people wo king in Combi-
na o ics and G aph Theo y a Ba celona, no coun ing hose people ha
9
The Beginnings J. L. A. Yeb a
wo k a o he places a e been ini ia ed he e.
Re e ences
[1] M.A. Fiol. A Boolean algeb a app oach o he cons uc ion o sna ks.
G aph Theo y, Comb. and Appl. Y. Ala i, G. Cha and, O.R. Oelle -
mann, and A.J. Schwenk., Eds. New Yo k: John Wiley & Sons, Vol.1,
493–524, 1991.
[2] M. Ga dne . Sna ks, Boojums and o he conjec u es ela ed o he
ou -colo map heo em. Scien ific Ame ican, 234:126–130, 1976.
[3] R. Isaacs. Infini e amilies o non i ial i alen g aphs which a e no
Tai colo able. Ame . Ma h. Mon hly, 82:221-239, 1975.
[4] N. Robe son, D. Sande s, P. Seymou , and R. Thomas. The Fou -
Colou Theo em. J. Comb. Theo y B, 70(1):2–44, 1997.
10