Claude Berge and the “Oulipo” - Lamsade
Contents
1. origin vertex furthermore most of the words in French relate also to graph theoretical concepts ami Ltoniens sentiers que auivent bien des cycles Figure 3 A Eulerian poem dedicated to C Berge Finally we would also like to mention an amusing application of hypergraphs to the creation of texts Many texts involve three characters that are linked by some ternary relation A very common relation is x takes y for z variants x prepares a plot with y against z x is in love with y married to z etc Each of such stories could then be described by a table summarizing the ternary relation The least interesting but most normal situation corresponds to the following table x x e x hehe he he NIN IN AN in which everyone is right about the identity of the others Obviously any variant of this ternary relation may give rise to interesting situations A common one is the following x e INKS he Jn fe fx N fa Mm IN in which a general quiproquo happens everyone is right about is own identity but is systematically wrong about the identity of the others Yet another interesting one is x y z Napol on Z y Z Napol on x Zz y x Napol on which might characterize a common psychiatric hospital The link between mathematics and literature has always been strong in the life of C Berge Quite significantly the las2. that the considered graph does not contain a Hamiltonian circuit but the removal of any vertex leads to a subgraph which does If such a graph exists what is the smallest one with respect to the number of vertices but the question can be set also with respect to the number of arcs C Berge gave the answer in the number 4 of the Biblioth que oulipienne the graph that he called Q6 see Figure 2 suits Q stands to pay tribute to his friend R Queneau 6 because this graph contains 6 vertices Notice that in spite of an ambiguous formulation by C Berge Q6 is not the only graph with the property stated above if we replace in Q6 the two circuits defined on three vertices on left and on right by any circuit defined on an odd number of vertices while keeping the pairs of arcs between homologous vertices of these two circuits we get a graph which does not contain a Hamiltonian circuit but such that the removal of any vertex leads to a subgraph which does but Q6 is the smallest one both with respect to the number of vertices and to the number of arcs Figure 2 The graph Q6 Claude Berge also practiced the so called Eulerian poem for which a graph is given where a verse is assigned to every arc by following any directed path one gets a reasonable text The example given by Figure 3 drawn from 8 is a graph of which the vertices are labelled G R A P H E S every verse is an alexandrine 12 feet and starts with the letter given to its
3. truit sa souche Tandis qu en frissonnant elle conjecturait L ami pr somptueux plus fou qu il ne parait Serrait sa souveraine une blo de farouche D un lien la fois oppresseur et charmant Dans Ouest enfoui dit elle 4 son amant iai C est l que l art fuit et d truit sa souche Et que la pyramide abolit l univers 1 Nul n entend le muet qui grenait des vers Azt que imperturbable a la touque impr cise Comme le perspicace inoui aux yeux verts Jeune libidineux que la froidure attise N offre pas de pactole ton gardien pervers Si le verbe jaillit que l Inca prosaise D un tel triomphateur ne trouble le diamant M me Xipe Totec tout doucement s enlise We leave to the reader the joy of deciphering this stylistic tour de force several tricks are involved The contributions of C Berge to Oulipo are diverse see for instance 2 see also 7 for more detailed materials about C Berge s contributions to the Oulipo In number 4 of the Biblioth que oulipienne 3 dedicated to R Queneau he considers Queneau s booklet Cent mille milliards de po mes 13 from a graph theoretic point of view Remember that this booklet contains ten sonnets by picking one of the ten first verses of these ten sonnets then one of the ten second verses of these ten sonnets and so on until picking a fourteenth verse among the ten last verses of the ten sonnets we may build a n
4. a systematic way formal constraints on the production of literary texts Although poets had explored for years the formal constraints of versification the originality of the group was to develop new or rarely studied constraints and to explore them systematically With this objective in mind the collaboration between writers and mathematicians proved extremely useful and Oulipo is considered to be among the most influential literary groups in France in the twentieth century The group is still active today According to the rules of the group Claude Berge will be excus pour cause de d c s at each meeting of Oulipo It is impossible here to give a complete overview of the incredible variety of constraints that the members of the group have explored and are still exploring It is nevertheless quite certain that Claude Berge has participated in the development and study of many of them besides producing his own texts Georges Perec was perhaps one of the most talented and prolific member of Oulipo In his book La Vie mode d emploi 12 Perec tells a story happening in a building of ten floors with ten rooms in each floor based on the rather recent at that time discovery of orthogonal Latin squares of size 10 it is a 10 by 10 array in each entry of which we have one of the numbers 1 to 10 and one letter a b c h i j these are arranged in such a way that in each row and in each column all figures are different and all letters a
5. Claude Berge and the Oulipo Denis Bouyssou Dominique de Werra2 Olivier Hudry 1 CNRS LAMSADE universit Paris Dauphine Place de Lattre de Tassigny 75775 Paris Cedex 16 France bouyssou lamsade dauphine fr 2 EPFL CE Ecublens 1015 Lausanne Switzerland dewerra ima epfl ch 3 ENST 46 rue Barrault 75634 Paris Cedex 13 France hudry enst fr Claude Berge June 5 1926 June 30 2002 is well known in the Operational Research community for his path breaking contributions to graph theory He received several awards for his scientific achievements including the EURO Gold Medal 1989 and the Euler Prize 1995 jointly with R L Graham The name of Claude Berge is likely to remain in history for several other reasons For instance he was an expert in the Asmat art from New Guinea He was himself a famous sculptor We would like here to mention yet another facet of Claude Berge He was a founding member of Oulipo for OUvroir de LItt rature POtentielle i e workroom of potential literature This group was created on 24 November 1960 under the impulsion of Raymond Queneau and Fran ois Le Lionnais the other founding members were Albert Marie Schmidt Jean Queval Jean Lescure Jacques Duchateau and Jacques Bens they were joined later by several well known members including Italo Calvino Harry Mattews Georges Perec and Jacques Roubaud Oulipo was a group of writers and mathematicians aiming at exploring in
6. ew poem there are 10 4 such possibilities hence the title of the booklet We may associate a vertex to each one of the 140 verses of the ten sonnets and link two vertices x and y by the arc an arc is a directed edge x y if the rank of the verse y in y s poem is the rank of the verse x in x s poem plus 1 Thus we get a multi layered directed graph without circuit a circuit is a directed cycle and with 14 layers and 10 vertices per layer Like C Berge we may then consider that the construction proposed by R Queneau is a directed path in this graph starting from any vertex of the first layer and ending at any vertex of the last layer Instead of a graph without circuit C Berge suggests a graph without any cocircuit remember that a cocircuit is a nonempty set A of arcs such that if we call X the set of the heads of the arcs of A then the tails of all the arcs of A are outside X in other words if Y denotes any proper subset of vertices of a graph G without any cocircuit there will always be at least one arc going inside Y and one arc going outside Y in G see for instance 1 for more details the verses still being associated with the vertices Moreover he requires that if the obtained poem contains all the verses exaclty once then it is impossible to repeat the first verse while respecting the construction process we must follow the arcs but this must become possible if any vertex is removed In graph theoretic terms it means
7. ion though the material forming the figures remains the same Figure 1 15 dwarfs if the picture is cut according to the lines and if the two upper parts are switched then the number of dwarfs is no longer 15 Similarly in La Reine azt que C Berge designs a sonnet hence with 14 verses of 12 feet and reorganizes these 14 verses into a poem of 15 verses still of 12 feet How can this be possible First consider the 14 verse sonnet below on left Then split the verses at the points enhanced by vertical lines and switch the right parts of the first lines until the empty line included with the right parts of the lines located after the empty line while keeping the empty line between these two parts This gives another poem with 15 verses of 12 feet Tandis qu en frissonnant elle grenait des vers L Azt que imperturbable la touque impr cise Serrait sa souveraine une blonde aux yeux verts D un lien libidineux que la froidure attise Dans Ouest enfoui dit elle son amant pervers C est l que art jaillit que I Inca prosaise Et que la pyramide abolit l univers Nul n entend le muet qui tout doucement s enlise Comme le perspicace inouil conjecturait Jeune ami pr somptueux plus fou qu il ne parait N offre pas de pactole ton gardien farouche Si le verbe la fois oppresseur et charmant D un tel triomphateur ne trouble le diamant mes M me Xipe Totec fuit et d
8. oi Zulma CNRS collection Manuscrits Paris 1993 10 D Knuth s home page http www cs faculty stanford edu uno retd html 11 G Perec La Disparition Deno l Paris 1969 12 G Perec La Vie mode d emploi Hachette Paris 1978 13 R Queneau Cent mille milliards de po mes Gallimard Paris 1961
9. re different and furthermore all contents of the 100 entries are different the stories of the 100 rooms of this 10 x 10 building are told consecutively by following an order which is the one of a knight making a Hamiltonian tour in a 10 x 10 chessboard C Berge helped G Perec in devising this structure see 9 for more details about the design of La Vie mode d emploi novel that D E Knuth places in 10 as one of the most important of the century Similarly La Disparition 11 still by G Perec is a lipogram i e a text written without a given 66 99 letter namely without any e though this is the most frequent letter in French it has been translated in English as A Void still without any e although e is also the most frequent letter in English With this respect the short story Qui a tu le duc de Densmore 5 Who killed the Duke of Densmore is surely the most famous written contribution of C Berge to the Oulipo In this detective short story written in 1994 C Berge applies a graph theoretic theorem due to G Haj s in order to identify the killer Prior to this short story C Berge published in 1983 La Reine azt que 4 The Aztec Queen in the style of the geometric illusions by Sam Loyd or DeLand see Figure 1 these geometric illusions are based on pictures with figures such that when cut and reorganized in an appropriate way the number of figures is not the same before and after the reorganizat
10. t conference given by C Berge it was in Lausanne in 2001 see 6 dealt with Mathematics and Literature such a choice was not just a curious coincidence References 1 C Berge Graphs and Hypergraphs North Holland Amsterdam 1976 2 C Berge Stories of the one zero zero one nights in P Hansen D de Werra eds Regards sur la th orie des graphes Presses polytechniques romandes 1980 29 38 3 C Berge Le graphe Q6 Biblioth que oulipienne n 4 Paris 1977 New edition in J Roubaud ed La Biblioth que oulipienne Slatkine Gen ve Paris 1981 4 C Berge La Reine azt que ou contraintes pour un sonnet longueur variable Biblioth que oulipienne n 22 Paris 1983 New edition in 1990 Seghers Paris 5 C Berge Qui a tu le duc de Densmore Bibliotheque oulipienne n 67 Paris 1994 6 C Berge Math matiques et litt rature communication to Latsis symposium 2001 Combinatorial Optimization Trends and Perspectives Lausanne Switzerland 16 17 November 2001 7 D de Werra From Ali HamOR to the Duke of DensmORe A guided tour of combinatorial literature communication to EURO Thirtieth Anniversary 1975 2005 Brussels Belgium 28 January 2005 see http www euro online org dewerra doc for the material 8 P Hansen D de Werra eds Regards sur la th orie des graphes Presses polytechniques romandes 1980 9 H Hartje B Magn J Neefs Cahier des charges de la Vie mode d empl
Download Pdf Manuals
Related Search