« Ils sont autrui : moi romantique et conscience poético-socio-politique », Poéthique, Poésie et éthique (XVIe-XXIe siècles), colloque organisé les 22 et 23 novembre 2018 à l'Université Paris-Sorbonne par Alain Génetiot , actes à paraître dans le n°4-2019 de la RHLF.

« Ils sont autrui » : moi romantique et conscience poéticosocio-politique « La poésie est : vivre » écrit Tristan Corbière dans « Un jeune qui s'en va », poème clinique des Amours jaunes. Cette formule lapidaire pourrait résumer le déplacement radical du genre auquel aura procédé le mouvement romantique : la poésie n'étant plus définie par l'usage compté du vers, ni sa visée, ni son éventuelle virtuosité, mais avant tout par sa charge existentielle brute, sans objet. Ce qui peut s'entendre en deux sens qui demeurent coprésents : d'une part la poésie se vit, elle est vécue, elle est même devenue la condition de tout vivable, parce qu'elle est le principe d'un rapport au monde, ou musicalement sa clef. D'autre part, la poésie vaut pour vivre, elle revendique une fonction viatique, une utilité en acte qui ne passe pas par les circuits mondains ni économiques.

Tel est le parti pris de la poésie au moment du premier romantisme français. Elle ne se croit pas commise au simple commentaire du monde, à son accompagnement pianoté autour : elle s'en charge. Par conséquent, elle se mêle de politique. La porte comme son inquiétude propre et se noue inextricablement à ses enjeux. Elle permet de dater une époque où le poète se dit personnellement responsable de l'homme. Plus profondément encore, elle donne le nouveau cadre dans lequel se déploie la simple possibilité d'être humain, de jouir de ses sensations, d'accéder à un langage. Permettant non seulement de vivre mais de se sentir vivant, dans l'intensification de la vie nue et de ses micro-événements. Cette poésie se fonde sur la sincérité : ceci est ma vie. Prenez et vivez-la tous. Elle est véridiction, c'est-à-dire que le chant lyrique, à ce stade, dépend fondamentalement d'un pacte éthique, qui rend secondaire la question du code esthétique et générique.

Jean Delabroy le souligne, quand il commente dans « La poésie à l'abandon » le cataclysme provoqué par Lamartine en 1820 dans le champ littéraire. « Les Méditations posent ce qui va devenir la nouvelle légitimité poétique : la réduction existentielle -la réduction de la poésie à l'existence même 1 . » C'est en ce sens que les Méditations ont fait date ; elles ont su exprimer la surrection d'un sujet, et à travers lui de tout sujet. Par conséquent la poésie, au moment où elle tend à s'identifier au lyrisme personnel, c'est-à-dire au début du dix-neuvième siècle, n'est plus un métier. « La poésie n'était pas mon métier », écrit Lamartine dans la préface des Méditations, en 1849. « Ce n'était pas un art ». Il va jusqu'à affirmer : « Je n'étais pas poète ». Qu'est-ce que cette poétique qui trouve à se dire d'abord par la négative ? Une poésie déprise de la technè, de ses assignations esthétiques et sociales traditionnelles, qu'elles soient métriques ou idéologiques : une poésie qui soit la vie même, dans son surgissement et son risque, qui soit un « gémissement » ou un « cri » viscéral avant même d'être une parole, à savoir avant d'entrer dans l'ordre et les circulations policés du logos. Ce faisant, moins on est poète, plus on est poète. Le poète romantique est celui qui n'hésite pas à sortir de la poésie ; et par ce choix même de l'écart, à sortir la poésie d'elle-même. La révolution lyrique inaugurée par Lamartine tient avant tout à cela : à la façon dont il a su requalifier l'homme, donner de nouvelles cordes vibrantes à son coeur ; réinventer son corps de sorte qu'il soit tout entier l'instrument de sa propre musique, traversé par les souffles de la nature, touché par le contact d'autrui. Ainsi, la vie lyrique sera une façon de ne pas séparer la poésie et la vie.

La poésie ne se replie pas. Elle offre un « viatique pour l'improbable métier de vivre2 », selon la belle formule de Jean-Claude Pinson. Elle propose un mode, voire un modèle d'existence. Poète à présent est celui qui se définit dans l'extériorité à tout art, à la maîtrise d'une quelconque technique, qui se soustrait à l'espace hypernormatif du genre et à ses codes hérités pour affirmer d'abord ce rapport direct à la vie que veut dire dorénavant la poésie, dans son urgence, dans son actualité. « Il faut imaginer, écrit Dominique Dupart, que le lyrisme n'est pas seulement une doctrine poétique, une nouvelle façon d'écrire de la poésie », « mais également une tentative pour habiter idéalement l'espace qui nous entoure, inséparable d'une critique des moeurs du temps présent, puisque, pour que ce lyrisme là soit possible, il faut tout simplement changer le monde3 ».

On s'explique mieux en effet que pour les poètes romantiques, cette vie, il faille la changer. Qu'elle ne se limite pas à la peine de coeur, aux affects mélancoliques, à la chute des feuilles ni aux grands frissons climatiques. Car cette vie ne peut être réduite à un seul domaine. Le chant est par nature expansif. Il s'étend au monde. Le poète, dans sa nature vibratile, est intimement requis par toute souffrance, et sa réceptivité est posée d'emblée comme une caisse de résonance : tout y trouve un écho, le vent, les sentiments, la grande souffrance muette du peuple écrasé par la machine économique. Agir, changer l'homme, la vie -mais comment ? Rappelons la façon dont Jean-Claude Pinson définit la « poéthique ». Dans la proposition forte que fait ce néologisme, un mot en cache un autre, l'inclut comme sa raison (la poésie comprend l'éthique et en retour elle est transformée par elle), et ce faisant déplace l'ancienne poétique sans h, absorbée par des soucis d'ordre rhétoriques et génériques, vers une poéthique qui ouvre le champ de la poésie au monde. « La poéthique s'interrogera donc sur la capacité de la poésie à influer sur la teneur et le cours de l'existence », écrit Jean-Claude Pinson.

C'est pourquoi la poéthique se conçoit comme l' « invention de formes écrites qui ouvrent sur l'invention de formes de vie (ethos) 4 ». On a vu que le geste du poète romantique a changé la définition même de la poésie : il congédie la poésie comme forme formelle pour en faire « une forme de vie », traduite non plus en « langue des dieux », mais dans une langue que potentiellement tout le monde peut entendre et parler. C'est le temps où le poème s'élargit, pour reprendre un titre de Jean-Christophe Bailly5 . La « réduction existentielle » implique que la poésie soit la chose au monde la mieux partagée. Elle est ouverte à tout le monde, à ce que Jean-Claude Pinson appelle le « poétariat6 », tous les gens vivant dans le dénuement, et non seulement dans la privation matérielle, mais aussi dans le drame métaphysique d'être promis à la mort. La saillance de l'individu concerne bien évidemment le poète, mais aussi quiconque, dans son anonymat de lecteur ou d'écrivant.

Ceci est mon corps, dit Lamartine en substance dans la préface des Méditations : ceci est le nouvel instrument que je vous tends ouvertement par le geste de la poésie, c'est-à-dire « les fibres même du coeur de l'homme, touchées et émues par les innombrables frissons de l'âme et de la nature ». Cet instrument, tous vous l'avez. Il est accessible, gratuit, universel. Chacun devient capable de poésie. Cette caisse de résonance intime, élémentaire, elle est en tous, pour tous. Hugo pointe cette réversibilité, dans la préface des Contemplations : « Insensé qui crois que je ne suis pas toi ». Ce faisant, il incorpore les personnes grammaticales, en posant l'identité stricte entre le « je » et le « tu » qui superpose, en même temps qu'il confond les expériences, l'énonciation et son récepteur. Le statut de la première personne change : paradoxalement, le « je » se trouve extensible, échangeable et pluriel dans sa singularité même. L'indistinction fait loi : le « je » n'est légitime dans sa parole d'outretombe que parce qu'il parle au nom d'un « tu » ; il parle à la place, quel qu'il soit, de celui qui est tu. Cette potentialité poétique donne le signal démocratique d'un partage, qui est avant tout un « partage du sensible », comme l'a mis en valeur Jacques Rancière.

Une telle poésie a une valeur « éthopoïétique », comme le souligne avec force Jean-Claude Pinson, par sa capacité « à former l'ethos, le séjour d'un sujet ». Et cette valeur ne doit pas être considérée a priori comme une utopie, voire une marge dangereuse de la rêverie collective. En effet, les liens entre poésie et existence ont été trouvés. Lamartine les a appelés des « fibres » : c'est ce que sont devenues les anciennes cordes tendues de la lyre, ces boyaux retentissant sous le toucher. La Révolution française avait préparé cette mutation du sujet en orchestrant le soulèvement de l'individu, revendiquant, avec les droits politiques et civils, le droit inaliénable de sentir et d'exister, de se sentir exister. C'est pourquoi les voix des premiers romantiques français s'orientent vers ceux qui écoutent, qui pourront recevoir leurs paroles et être transformés par eux. Non pas seulement par tel ou tel message politique clair. Ou accessoirement. Ce qui compte avant tout, c'est qu'ils écrivent une poésie à vivre. Une poésie qui relie chacun à son récit destinal, et provoque par là une révolution intérieure, une nouvelle façon de sentir, de voir le monde et de se lier aux autres. Tout le monde a droit à la poésie signifie : tout le monde a droit à ses sensations, à son émotion, à son regard de contemplation, au retentissement de sa joie propre et de sa souffrance, dans un espace de respiration nouveau qui n'est ni celui d'une maîtrise des savoirs, ni celui des tâches écrasantes, ni de la répétition aliénante. Telle est l'idée obsédante, mantra romantique sans cesse décliné et repris : à nouveau sujet social et sensible, nouvelle politique d'écriture.

De même que la poésie devient potentiellement le fait de tous, la politique redevient, comme dans l'Antiquité, chose publique, mise en commun. Lamartine ou Hugo ont rendu éloquente l'intrication, dans leurs vies même, entre poésie et politique. Tout communique. Sans coupure. Lamartine commémore un idéal antique dans la préface des Méditations ou dans son Voyage en Orient : sur le modèle de Cicéron ou de César, il veut incarner l'« homme complet », capable à la fois de pensée et d'action, au lieu de n'être, sur le terrain politique, qu'un musicien amputé de ses mains.

« Orphée est courbé sur le monde » écrit Hugo dans son poème « Les Mages ». Telle est la fonction du poète, à ses yeux, autrement dit encore sa mission orphique, figurée dans cette posture mythique et comme figée hors du temps : non pas regarder en soi ni au loin ni river ses yeux au ciel, mais tenir le regard fixé sur le réel, en ce que le réel est ce qui désormais lui incombe. Voici un événement essentiel : le poète romantique est quelqu'un qui doit répondre du monde, et qui en a conscience. Il manifeste ce soin et ce souci qui le cassent et le plient en direction du sol. Il penche pour l'humanité, et c'est pourquoi il se voûte sur elle comme un second ciel, en un siècle où Dieu mourant fait défaut. Ainsi, quand la poésie n'est plus réductible à la reproduction d'un modèle préexistant, n'est plus mimétique d'une somme de discours sur le monde, elle peut coïncider avec son temps. On peut dire du poète romantique qu'il tire la poésie vers le contemporain. L'oblige à se tourner vers son époque. Les vers sillonnent le champ pragmatique. Peuvent-ils servir de scansion à l'espace public ?

On peut aller plus loin, en disant que Lamartine et Hugo, chacun à sa manière, parce qu'ils ont été des écrivains-hommes d'État, sans qu'on puisse démêler l'une de l'autre ces deux fonctions, ont été politiquement convertis par leur poésie. Rendant peu à peu cohérents leurs paroles et leurs actes, les accordant pour ainsi dire, et passant d'un monarchisme de droite à la gauche humanitaire. Ajoutons qu'à la différence des stratégies de politique oblique développées par certains poètes, qui feront dans leurs poèmes de la politique sans en parler (Paul Verlaine, et bien d'autres encore), les mages du premier romantisme optent résolument pour l'action directe : ils font de l'interventionnisme d'auteur à la Chambre des Députés. Quand ils prennent la parole, c'est pour dénoncer haut et fort l'esclavage (Lamartine) ou les misères (Hugo). La poésie devient ce rythme qui plaide pour le progrès. Donc le poète romantique monte à la tribune et revendique son bilinguisme, de sorte que l'instrumentation lyrique du corps humain va jouer contre la réification et l'instrumentalisation politique du corps populaire. L'homme n'est pas seul. Et pour reprendre une formule de Michel Deguy, la poésie n'est pas seule. De ces deux absences d'isolement on peut faire un état lyrique, et l'écrire aussi, comme une sorte de fantôme romantique, avec une majuscule, un État lyrique. Contre l'isolationnisme de la poésie, les poètes romantiques affirment haut et fort leur désir de ne plus faire monde à part ; de ne plus faire langue à part. Ils rejoignent la réalité. Lamartine, qui sera chef du gouvernement provisoire lors de la révolution de février 1848, entre en politique armé de la lyre. S'il joue de la poésie de chambre, comme on parle de musique de chambre, en inventant la formule de son toucher, peut-il faire entendre une poésie de la Chambre des Députés ?

La lyricisation démocratique du politique est-elle possible ? Utopie, rêve dangereux, m'arrêtera-t-on. On a vu les risques et les retombées de la grande « illusion lyrique » de février 1849, entre autres. L'immense espoir lyrique de changer la vie a pu dériver dans le sang, et changer les idées en flux de rhétorique un peu creuse, facile à ironiser par les sceptiques et les opposants. Dominique Dupart a montré à quel point les théoriciens de la gauche révolutionnaire et du communisme détestaient Lamartine, dénigré par Proudhon, discrédité par Engels et Marx, malgré quelques points de convergence. Il n'empêche. Le lyrisme démocratique a su rendre fortes et crédibles un certain nombre de valeurs issues de la Révolution française, avec leur excès potentiel et leur effilochement dans la folie : égalité, liberté, fraternité. Les grands mots devenant tantôt des héros, tantôt des assassins. Comment le poème d'un seul peut-il représenter (au sens large mais aussi au sens légal, politique) la communauté des coeurs sensibles ? Parler de poéthique dans le cas du premier romantisme, c'est se situer au noeud d'une contradiction apparente qu'il nous faut ici exposer. En effet, le lyrisme personnel qui s'invente à cette époque a rapidement été assimilé à une égologie aussi bruyante que larmoyante. « Je m'exprimais moi-même pour moi-même » écrit Lamartine en 1849, quand il fait retour sur ses Méditations. Ce faisant, il semble donner la formule du solipsisme dans quoi risque de s'enfermer la poésie, sans langue communicable et sans destinataire. Les relectures sont sévères et polémiques. Leconte de Lisle, par exemple, dans ses Poèmes antiques, en 1852, déclare la guerre au moi romantique et à ses représentants, en appelant à en finir avec « l'autolâtrie d'emprunt » de ces piètres comédiens. Selon lui, ces « moralistes sans principes communs » ont manqué à leur « apostolat » : ils forment une « race inconsistante et fanfaronne » qui se complait « dans une radicale ignorance de l'homme et du monde ». Une telle poétique, émanant d'histrions complaisants et narcissiques, coupés de leurs semblables, ne peut se revendiquer à ses yeux d'aucune dimension éthique. Comment donc déployer une poéthique à partir de ce qui risquerait fort d'isoler le sujet dans une expérience restreinte à soi ? Lamartine a répondu à ce reproche, qu'on lui adressait depuis longtemps et qu'il s'adressait à lui-même, dans un texte important, qui donne lieu à une véritable palinodie. Chant inverse du poète lyrique, devant la maladie de celui qu'il appelle « Frère », dans un poème des Recueillements poétiques de 1839, intitulé « À M. Félix Guillemardet, sur sa maladie ». Le mal terrible dont souffre ce frère, dénommé Felix non sans ironie du sort, ajoute la paralysie à l'aphasie, lui qui se trouve condamné « À penser sans parler, à sentir sans organe,/ À subir des vivants les mille impressions / Sans pouvoir t'y mêler du regard ou du geste ». Un tel sujet exacerbe la problématique de la vie lyrique. Voilà un corps passif, comme damné par la maladie, privé de toute expressivité, de toute mobilité. Il ne peut ni bouger ni parler : à travers lui transparaît un corps social sans aucune liberté d'action ni de représentativité politique. Or le poète lui adresse sa parole. Il commence par se repentir d'une époque du lyrisme personnel qu'il identifie à un « égoïsme » : « Je resserrais en moi l'univers amoindri / Dans l'égoïsme étroit d'une fausse pensée ». Il s'y dépeint, à ses débuts, uniquement préoccupé du « propre », dans une relecture intraitable des Méditations poétiques, comme si cet âge du moi devait absolument être derrière lui, ne correspondant plus en rien à l'engagement effectif et total du sujet lyrique dans la vie politique :

Frère, le temps n'est plus où j'écoutais mon âme Se plaindre et soupirer comme une faible femme Qui de sa propre voix soi-même s'attendrit Le temps n'est plus. Le poète est sorti de cette parole pour soi seul. « Erreur d'un insecte », dit-il. Après la phase d'autocritique (« O honte ! O repentir ! »), le sujet lyrique sort de lui-même. Vivre, c'est se détacher de soi. Dépasser ce moment où, comme il dit, « ma personnalité remplissait la nature ». Il refuse désormais que cette « neuve énergie » qu'il sentait alors dans le deuil lui « cache les maux d'autrui ».

Puis mon coeur, insensible à ses propres misères, S'est élargi plus tard aux douleurs de mes frères ;

Ce qui envahit alors le poème, ce sont les références à la fable christique. Le sujet lyrique vit sa passion. C'est-à-dire qu'il se situe en ce point précis où le moi, se dilatant à tous, « a gémi toutes les douleurs », quand sa « tristesse » a pu « contenir seule assez d'agonie / Pour exprimer l'humanité ! » Le Christ est par excellence un poète lyrique ; son exemple sert de propédeutique. Il initie le sujet lamartinien à sa propre vocation, qui consiste, on l'a entendu, à « exprimer l'humanité ». L'exemple divin est un guide ; il transcende la personne en l'initiant à l'impersonnalité d'une vie pour tous. Car ce que le poète retient surtout du Christ, ce n'est pas la dimension surhumaine ni l'impunité divine que donne l'immortalité. Au contraire, la vie lyrique passe par la mort. Elle est l'épreuve de la mortalité ; elle en est l'invention en littérature. Elle prend acte de la fragilité éphémère de la vie, de ses brisures, de ses failles, de ses impuissances. Et le Christ même n'a pu en être exempt : il a dû passer par la mort, seule épreuve qui permet de communier vraiment avec la souffrance multiple, immense, sans nom, de tous les corps torturés par eux-mêmes.

Le dire lyrique n'accède à la voix de tous qu'en s'ouvrant à ce silence tragique des homme sans voix, livrés à la mort. Il n'est même pas question, dans ce poème des Recueillements, de bien-être ni de vivre mieux, d'améliorer les conditions d'existence par le confort ou la liberté. Le scénario est plus radical encore : il s'agit d'interroger l'être-au-monde de quelqu'un qui est privé de tout, non pas matériellement, mais par son corps même. Qui n'a pas d'existence. Cet état de nudité radicale désencombre le vrai lieu du drame social et politique : il dit la parole qu'il faut, dans l'urgence, faire retentir au nom de tous ceux qui n'ont pas de voix, ni voix lyriques, ni voix d'électeurs, mais qui sont renvoyés à un néant d'être sans accéder à la moindre capacité de vie terrestre. Ce Christ lyrique se politise. Il légitime l'entrée du poète dans « l'arène humaine », ses combats, son militantisme et ses discours de lutte à la Chambre des Députés. Le « je » égocentré du lyrisme personnel s'ouvre à la misère existentielle d'autrui par la compassion : le pâtir-avec, qui élargit ce « je » à une parole engagée, transitive, vibrante du sort mortel d'autrui.

En ce sens, le poète lyrique est un sauveur moderne. Il a le don de se faire christ : il a développé un sens aigu du sacrifice. L'individu n'est personne, s'il n'est pas porté à la puissance de l'universel. Il émet non plus une poésie centrée sur soi, sur sa seule souffrance, son coeur seul. Mais une poésie qui enregistre le cri de tous, qui prenne sur soi, à la place de tous les muets de l'Histoire, la grande pathologie collective. Une telle poésie non-personnelle, en ce sens, est faite par tous. Le « je » revendique un mode d'être commun qui n'est pas d'abord celui de la coexistence sensible, mais qui commence par poser la préexistence ontologique du « tu », du « frère ». Ce geste réinvente l'énonciation en première personne comme voix détachée du moi anecdotique, désincarcérée de ses propres affects. Le poète lyrique converti et recrucifié par la souffrance d'autrui s'en fait le porte-parole.

Il faut donc rappeler que cette poéthique du premier romantisme en apparence autocentrée prend pour sujet un « je » fortement individualisé, mais aussi poreux et substituable à volonté, ce qui le maintient dans l'ouverture et le souci de ses « frères ». Quand on se penche sur le cas du lyrisme personnel, en effet, on s'aperçoit vite qu'il échappe à la caricature à laquelle il est trop souvent réduit par une lecture téléologique. Ce sujet saillant qui parle, cet hyper-sujet qui s'affirme en son nom propre, est dans le même temps un infra-sujet effacé et évidé, ici devant l'évidence de la souffrance d'autrui. « Oh ! quand je pense à toi, moi-même je m'oublie ! » s'écrie le sujet lyrique lamartinien dans « À M. Felix Guillemardet ». Mettant en valeur au centre du vers ce chiasme qui assure l'échange entre le « toi » et le « moi-même ». Infiniment réceptif, le moi lyrique se dilate et se transfuse dans l'autre par un processus d'empathie -rappelons que le pacte lyrique articule, comme l'a souligné Antonio Rodriguez, « une mise en forme affective du pâtir humain ». Dans cette rencontre et cette coïncidence des pâtir le moi s'oublie et libère sa place, se désignant potentiellement comme la bouche de tous : autrement dit, l'expression libre des affects et des souffrances qui parle par le poème. C'est cette forme apersonnelle de l'affectivité7 qui nous intéresse ici, avec toutes les résonances sensibles mais aussi idéologiques et politiques qui se trouvent impliquées dans ce processus de substitution à volonté. La personne lyrique n'est personne : la « vraie vie » lyrique engage une formidable disponibilité des personnes grammaticales -une vacance énonciative.

Hugo approfondit cette mission de se faire « mage » à travers la question cruciale de la subjectivation. Qu'est-ce qu'être un mage au moment du Romantisme ? Avoir des pouvoirs surnaturels ? Non. Ses pouvoirs, le mage les tient de sa voyance et de sa véridiction. De sa capacité à vivre pour tous, et à le dire à la place de tous [START_REF] Guernesey | la mer aride à perte de vue, le désert d'hommes, la vie qui se retire vers le papier. Entre autres, Les Misérables, tout un peuple des bas-fonds à faire exister en littérature[END_REF] . Or les poètes, comme Orphée, ne sont pas seulement de doux chanteurs charmant jusqu'aux bêtes. Ils sont, insiste Hugo, « producteurs de civilisation ». Significativement Lamartine, à partir de 1852, a lancé son journal sous ce titre, Le Civilisateur. Il s'y est intéressé au « génie », au « grand homme », à savoir celui qui a vu grand, et trouvé la formule d'une avancée : Homère, Gutenberg, Colomb, chacun dans sa sphère, furent des poètes du réel, des révélateurs d'humanité. Les génies sont utiles. Ils trouvent comment exercer un impact sur le réel pour changer la vie.

Il était question tout à l'heure des circulations entre pronoms personnels. Georges Gusdorf 9 , dans l'introduction de L'Homme romantique, dessine ce qu'il appelle une « nouvelle grammaire de la société » : « L'âge romantique, au point de vue psychologique, moral, esthétique et religieux, est le temps de la première personne, le temps du je, qui peut être couplé avec le tu, et qui, associé à d'autres je, peut constituer un nous, dont la revendication donne à l'espace social et politique des colorations nouvelles ». Comment se construit ce « nous » romantique ? Les poèmes réfléchissent implicitement sur cette première personne du pluriel, « nous », qui n'est pas une personne, comme le fait remarquer Jean-Christophe Bailly, mais bien une jonction instable entre « je » et « tu », dans la « nostration 10 » des communautés qui ponctuent l'Histoire. Ce passage du singulier à la pluralité, comment le poète lyrique y parvient-il ? Quelle vie partageable offre-t-il à la communauté des lecteurs, et par-delà, à la communauté sociale et politique ?

Hugo se livre à une petite anthropologie de la création artistique dans un texte qui se penche sur le rôle du « génie ». Les échos avec son oeuvre poétique sont nombreux, en particulier avec le poème des « Mages » : « Comme ils regardent, ces Messies ! » Paul Bénichou, dans Les Mages romantiques [START_REF] Bénichou | Les Mages romantiques[END_REF] , c'était en 1988, a mis en lumière de façon décisive la vocation messianique de ces nouveaux prophètes, soucieux d'exercer un véritable magistère spirituel. Par l'intensité de leur existence, par leur don pour sonder l'ombre, « Ils sont. Savent-ils ce qu'ils sont ? » Grâce à eux, « le muet renonce à se taire », et « une sorte de Dieu fluide / coule aux veines du genre humain ». Le poète parle d'eux à la troisième personne du pluriel, les laissant dans une forme de distance sacrée. Le « nous », au contraire, c'est celui des simples vivants, les plus démunis : « Nous vivons, debout à l'entrée / De la mort, gouffre illimité ». Ceux Ainsi, les génies sont dans la mesure où ils n'ont pas de moi : la seule façon qu'ils ont de se saisir d'eux-mêmes, c'est par le détour de l'autre. Mais dans ce mouvement d'identification, ils abandonnent leur être-pour-eux-mêmes, qui correspond au mouvement instinctif et naturel d'une conscience élémentaire. Les génies dépassent la pathologie de l'être pour-soi, qui serait aliénante pour ces géants. S'ils expérimentent l'existence, c'est uniquement par projection : par ce mouvement qui les porte au-dehors d'eux-mêmes vers ceux-qui-n'ont-pas-de-vie, qui échouent à devenir un moi, et qui sous-vivent, pris dans la masse, portés et déchirés par les intérêts des besoins et des pulsions. Car les autres sont d'abord, ils sont avant et ils sont à la place du moi.

Hugo ajoute à ce portrait des génies : « Ils souffrent la souffrance extérieure, nous l'avons dit ; ils saignent tout le sang qui coule ; ils pleurent les pleurs de tous les yeux ». Ces génies connaissent une forme étrange d'excorporation : dans un transfert d'affects, ils souffrent à l'extérieur d'eux-mêmes, pleurent les larmes des autres et meurent de leurs morts. Tel est le paradoxe du génie hugolien : le plus intime et le moins partageable de ce qui arrive aux autres, ils le portent et le vivent en personne. Le processus de désegotisation va de pair avec l'affirmation d'une parole et d'une action : se perdre en devient la condition. Ces êtres à l'abandon que sont les génies ne peuvent donc être assimilés à des hommes passifs et asthéniques, souffrant d'un déficit d'identité. Ce qui leur arrive est tout différent. Ils se dépassent eux-mêmes et dilatent les capacités du moi jusqu'aux limites du possible : celles qui les portent à être-autre. Ils expérimentent une transitivité superlative, qui les tourne vers autrui. « Penser est une générosité ». Tel est leur don : talent et donation.

Loin de l'image rétractile qu'a pu donner le philosophe cartésien enfermé dans son poêle, la pensée est donc par définition expansive. On aura trop glosé sur l'égoïsme du poète lyrique, on lui aura taillé sans autre forme de procès la réputation d'être complaisant et narcissique. Le « je » du poète personnel est au contraire, quand il s'abandonne, un sujet pulvérisé. Il ne s'appartient plus. Le passage par la première personne n'est qu'une étape dans le processus d'effacement et de dilatation qui met à mal la catégorie étroite de l'ego. Cet hypersujet qu'est pour Hugo le « génie » manifeste des capacités d'empathie telles qu'il ressuscite, comme le sujet lamartinien après son mea culpa, la figure du Christ, pour faire du poète l'être le plus exposé, voire une sorte de martyre moderne de l'humanité. La rédemption catholique par la souffrance donne la note. Mais ce n'est pas tout. C'est toute la conception du sujet qui s'articule autour de cette image encore religieuse, qui garde de cette transposition une aura laïque. Poète est celui qui fait la somme de toutes les singularités souffrantes et en porte, par procuration, la plainte et l'espoir. Il compte au nom des fils de la finitude. C'est à ce titre qu'il parle. Et qu'il est sacrifié.

Pour conclure, disons que les poètes du premier romantisme, dans la mesure où ils ont su recharger le lyrisme avec de la pensée et de l'empathie, ont réinventé la poésie lyrique comme forme de vie et orientation vers la vie. La vie active, la vie élargie, dans la dilution des catégories grammaticales de personne. Je, c'est il. C'est tu, c'est tous. Le singulier devient pluriel. Le moi du lyrisme personnel, passant pour un triste individu, fermé sur lui-même, devient un sujet impersonnel et universel. L'expressivité souffrante du moi lyrique dit l'extension de la parole sensible et réceptive au « nous » d'une communauté à la recherche d'elle-même. La politique est peut-être, au fondement, une question d'empathie (Rousseau ne disait pas autre chose quand il faisait de la pitié le premier « sentiment naturel », qui instaure le lien social, les lois, les moeurs, la vertu12 ). La circulation des idées s'appuie sur le partage des affects dans une communauté sensible où nul ne peut ignorer ni écraser son prochain, puisque précisément les identités se substituent les unes aux autres dans l'ouverture. Le mal qu'on fait à l'un, on le fait à tous. Dans la même logique, écrire un poème, c'est l'écrire par tous et pour tous. Ces jonctions, ces nouages retravaillent la langue et les configurations politiques à travers elle.

Aurélie Foglia Université Paris 3-Sorbonne Nouvelle

  -là, nous donc, attendons la lumière et la vie venue des mages, ce sang « d'une sorte de Dieu » qu'ils nous transfusent. Hugo décrit ainsi les « génies » dans ses Proses philosophiques : « ils ont un moi incorruptible, parce qu'il est impersonnel. Leur moi, désintéressé d'eux-mêmes, indicateur perpétuel de sacrifice et de dévouement, les déborde et se répand autour d'eux. Le moi des grandes âmes tend toujours à se faire collectif. » Et un peu plus loin, il déjoue la logique traditionnelle des pronoms personnels en affirmant : « Ils sont autrui. Autrui, c'est là leur moi. Vivre en soi seul est une maladie. L'âme est astre, et doit rayonner. » Il n'est plus même question d'altruisme ni de porosité. C'est audelà. Dans cette formule (« Ils sont autrui »), qui décline à sa façon forte le motif célèbre du « je est un autre », le sujet se démet de son identité au profit d'une altération radicale qui aboutit à l'oxymore. Ce qui définit les génies, c'est d'être les autres. Leur vie n'existe que dans son extériorisation constante. Le « génie » porte l'aspiration à une vie collective et propose la construction d'un nouvel ethos qui brouille les limites du « je » et du « tu », et invalide la distinction entre singulier et pluriel.

Jean Delabroy, « La poésie à l'abandon », Un Ange passe. Lamartine et le féminin, sous la direction de Jean-Pierre Reynaud, Klincksieck, 1997, p. 30.

Jean-Claude Pinson, Poéthique, une autothéorie, Champ Vallon, 2013, p. 5.

Dominique Dupart, « Le rouet est silencieux dans la vallée : Lamartine, Flaubert, Proudhon et Marx », Lamartine ou la vie lyrique, sous la direction d'Aurélie Foglia et Laurent Zimmermann, Textuel, 2018, p. 67.

Jean-Claude Pinson, Poéthique, p. 91.

Jean-Christophe Bailly, L'Élargissement du poème, Christian Bourgeois éditeur, 2015.

Jean-Claude Pinson, Poéthique, op. cit., p. 24. « Mais en même temps que sa désinence suggère les difficultés subies (précarité, pauvreté), le mot peut faire signe aussi vers des limites assumées, vers un sens revendiqué de la finitude écologique autant que métaphysique, s'il est vrai que la poésie, comme a pu le soutenir Sartre, est dans la littérature le genre le mieux à même de dire ce « guignon » qui, selon lui, fait le fond de toute condition humaine (de toute existence « dévalant » inéluctablement vers la mort.)

On pourra consulter à ce sujet Éloge de l'hypersensible d'Évelyne Grossman (Minuit, 2017).

Jean-Jacques Rousseau, Discours sur l'origine de l'inégalité parmi les hommes.


Pierre Fraigniaud
email: pierre.fraigniaud@liafa.jussieu.fr.

Cyril Gavoille
email: gavoille@labri.fr

David Ilcinkas
email: david.ilcinkas@labri.fr.

Andrzej Pelc
email: pelc@uqo.ca.

Distributed Computing with Advice: Information Sensitivity of Graph Coloring §

Keywords: network algorithm, graph coloring, distributed computing

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations.

The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

Introduction

This work is a part of a recent project aiming at studying the quantitative impact of knowledge on the efficiency when computing with distributed entities (nodes of a distributed system, mobile users in ad hoc networks, etc.). Indeed, as observed by Linial [START_REF]Locality in distributed graph algorithms[END_REF], "within the various computational models for parallel computers, the limitations that follow from the local nature of the computation are specific to the distributed context". Two frameworks have been considered for analyzing the limitations incurred by the local nature of distributed computations. One aims at identifying which tasks can or cannot be computed locally, i.e., when every node can acquire knowledge only about the nodes that are at constant distance from it. Surprisingly, non-trivial tasks can be achieved locally [START_REF] Naor | What can be computed locally?[END_REF]. This is for instance the case for weak-coloring, a basis for a solution to some resource allocation problems. However, many important problems in distributed computing do not have a local solution [START_REF] Kuhn | What cannot be computed Locally! In 23th[END_REF]. This is the case of computing an approximate minimum vertex cover or an approximate minimum dominating set.

The other framework that has been considered is distributed computing with advice.

In this framework, the computing entities can be given information about the instance of the considered problem. The traditional approach is actually qualitative in the sense that algorithms are designed or impossibility results are proved under the assumption that the nodes are aware of specific parameters, e.g., the size of the network. It was proved that the impact of knowledge concerning the environment is significant in many areas of distributed computing, as witnessed by [START_REF] Fich | Hundreds of impossibility results for distributed computing[END_REF][START_REF] Lynch | A hundred impossibility proofs for distributed computing[END_REF] where a lot of impossibility results and lower bounds are surveyed, many of them depending on whether or not the nodes are provided with partial knowledge of the topology of the network. A quantitative approach was recently introduced in [START_REF] Fraigniaud | Oracle size: a new measure of difficulty for communication tasks[END_REF], in which limitations of local computation can be estimated by establishing tradeoffs between the efficiency of the computation (number of steps, number of messages, etc.) and the amount of information provided to the nodes about their environment, independently of what kind of information they receive.

More precisely, we consider network computing with advice in the following context.

A network is modeled as an undirected graph where links represent communication channels between nodes. Nodes of n-node networks have distinct IDs from {1, . . . , n}, and communication ports at a node of degree d are labeled by distinct integers from {1, . . . , d}.

A priori, every node knows only its own ID and the labels of its ports. All additional knowledge available to the nodes of the graph (in particular knowledge concerning the topology and the labels of the rest of the graph) is modeled by an oracle providing advice. An oracle is a function O whose arguments are networks. The value O(G) for a network G = (V, E), called the advice provided by the oracle to this graph, is a function f : V → {0, 1} * . This function assigns a finite binary string to every node v of the graph.

Intuitively, the oracle looks at the entire labeled graph with IDs and assigns to every node some information, coded as a string of bits. A node v is informed by the oracle if the string f (v) is non-empty. The size of the advice given by the oracle to a given graph G is the sum of the lengths of all strings it assigns to nodes. Hence this size is a measure of the amount of information about the graph, available to its nodes. Clearly, the size of advice is not smaller than the number of informed nodes. The objective is to establish tradeoffs between the size of the advice and the computational efficiency of the network. Specifically, we focus on the distributed graph coloring problem, one of the most challenging problems in network computing for its practical applications, e.g., in radio networks [START_REF] Moscibroda | Coloring unstructured radio networks[END_REF], and for its relation with many other problems such as maximal independent set (MIS) [START_REF] Kuhn | What cannot be computed Locally! In 23th[END_REF][START_REF] Panconesi | Improved distributed algorithms for coloring and network decomposition problems[END_REF] and symmetry breaking [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF]. Initially, each node knows its ID from {1, . . . , n}. The c-coloring problem requires each node to compute a color in {1, . . . , c}, under the constraint that any two adjacent nodes have different colors. Computation proceeds in rounds following Linial's model defined in [START_REF]Locality in distributed graph algorithms[END_REF] (a.k.a., LOCAL model [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF]).

In each round, a node sends a message to each of its neighbors, receives messages from each of its neighbors, and performs some local computations. The LOCAL model does not put any limit on the message size and any restrictions on local computations because it is designed to estimate limitations of locality. The complexity of c-coloring a graph G is measured by the number of rounds required to compute a proper c-coloring. There is an obvious relation between the complexity of c-coloring and the maximum distance between two nodes that exchange information during the computation.

Coloring graphs using advice provided by an oracle O consists in designing an algorithm that is unaware of the graph G at hand but colors it distributively, as long as every node v of the graph G is provided with the string of bits f (v), where f = O(G).

Trivially, an advice of size O(n log c) bits that provides the appropriate color to each node yields a coloring algorithm working in 0 rounds. On the other hand, an advice of size 0, i.e., providing no information, yields an algorithm running in t(n, c) rounds where t(n, c)

is the complexity of the coloring problem in the usual distributed setting (i.e., with no advice).

The main objective of studying network computations with advice is to establish tradeoffs between these two extreme cases. Different forms of tradeoffs are illustrated in Figure 1. This figure plots the execution time as a function of the size of advice (i.e., the amount of information given to the nodes). The execution time decreases as the size of advice increases, like, e.g., the dashed curve. Depending on how quickly the curve drops down enables to roughly classify problems as "sensitive" or "insensitive" to information.

A problem is information sensitive if few bits of information given to the nodes enable to decrease drastically the execution time. Conversely, a problem is information insensitive if the oracle must give a lot of information to the nodes for the execution time to decrease significantly. In this paper, we study the information sensitivity of graph coloring.

Our results

To study the information sensitivity of graph coloring, we focus on lower bounds on the size of advice necessary for fast distributed coloring of cycles and trees, two important cases analyzed in depth by Linial in his seminal paper [START_REF]Locality in distributed graph algorithms[END_REF] (cf. also [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF]).

We show that coloring a cycle is information insensitive. Precisely, we show that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to beat the Θ(log * n) time of 3-coloring a cycle, where log (k) n denotes k iterations of log n. This shows a huge gap between 3-coloring in time Θ(log * n) and 3-coloring below this time: while the first can be done without any advice [START_REF] Cole | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms[END_REF], the second requires almost as much information as if colors were explicitly assigned to nodes (which would take O(n) bits).

The result for cycles easily extends to oriented trees (i.e., rooted trees in which every node in the tree knows its parent in the tree), proving that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to beat the O(log * n) time of 3-coloring an oriented tree [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF]. Coloring an oriented tree is thus also information insensitive.

The power of orienting a tree (i.e., giving an orientation of its edges toward a root), from the point of view of distributed coloring, was known since Linial [START_REF]Locality in distributed graph algorithms[END_REF] proved that no algorithm can color the d-regular unoriented tree of radius r in time at most 2 3 r by fewer that 1 2 √ d colors. Hence 3-coloring unoriented trees essentially requires Θ(D) rounds, where D is the diameter of the tree. Therefore, informing every node of the port leading to its parent in the tree results in decreasing the time of 3-coloring from Ω(D) to O(log * n). We revisit this result using our quantitative approach. Precisely, we aim at computing the amount of advice required to reach the O(log * n) time bound. It is known that O(n log log n) bits of advice enable to orient a tree (i.e., to select a root, and to give to every node the port number of the edge leading to its parent) with an algorithm working in 0 rounds [START_REF] Cohen | Labeling Schemes for Tree Representation[END_REF], and O(n) bits of advice enable to orient a tree with an algorithm working in 1 round [START_REF] Cohen | Label-Guided Graph Exploration by a Finite Automaton[END_REF]. However, 3-coloring a tree in time Θ(log * n) does not necessarily require to orient the tree. Nevertheless, we show that, for any constant k, Ω(n/ log (k) n) bits of advice are needed in order to 3-color all n-node unoriented trees in time Θ(log * n). Thus, while for oriented trees 3-coloring in time O(log * n) can be done without any additional information [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF], achieving the same efficiency for arbitrary trees requires almost as much information as if colors were explicitly assigned to nodes.

Finally, both for cycles and trees, even if oriented, we also show that Ω(n) bits of advice are needed for 3-coloring in constant time (i.e., for 3-coloring to become a locally solvable problem). Thus constant-time coloring requires essentially as much information as if colors were explicitly assigned to nodes. In fact, our lower bounds do not hold only for the total number of bits of advice given to nodes but also for the number of nodes that must be informed (i.e., the number of nodes that are given at least one bit of advice).

Although we formulate our results for the task of 3-coloring, they remain true for coloring with any constant number of colors, by slight technical modification of the proofs.

While our lower bound proofs present different technical challenges in the case of the cycle and that of trees, the underlying idea is similar in both cases. Linial [START_REF]Locality in distributed graph algorithms[END_REF] constructed the neighborhood graph N[G] of a graph G in order to estimate the time of coloring G using the chromatic number of N[G]. Since in our case there is an oracle giving advice to nodes, we have to use a more complex tool in the lower bound argument.

We also argue about the chromatic number of a suitably chosen graph H in order to bound coloring time of G. However, in our case, this graph depends on the oracle as well as on the number of communication rounds, and hence on the graph G. This makes it very irregularly structured. We show that, if the number of nodes of G informed by the oracle is not too large, then H has a large chromatic number, and thus forces large coloring time of G. (Equivalently, if G can be colored fast then the advice must be large.)

The main difficulty in our argument is to show the existence of a regularly structured subgraph (whose chromatic number can be bounded from below) in the highly irregularly structured graph H.

Related work

Because of the intrinsic difficulty of computing the chromatic number of a graph in the sequential setting [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF], or even to approximate it [START_REF] Bellare | Free Bits, PCPs, and Nonapproximability -Towards Tight Results[END_REF][START_REF] Feige | Zero Knowledge and the Chromatic Number[END_REF], the distributed computing literature dealing with graph coloring mostly focuses on the (∆+ 1)-coloring problem, where ∆ denotes the maximum degree of the graph. In fact, the interest expressed for the (∆ + 1)coloring problem is also due to its intriguing relation with the maximal independent set (MIS) problem, already underlined by Linial in [START_REF]Locality in distributed graph algorithms[END_REF]. In particular, combining the best known algorithms for MIS [START_REF] Alon | A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem[END_REF][START_REF] Luby | A Simple Parallel Algorithm for the Maximal Independent Set Problem[END_REF] with the reduction from (∆ + 1)-coloring to MIS by Linial yields a randomized (∆ + 1)-coloring algorithm working in expected time O(log n).

Using techniques described in [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF] and [START_REF] Panconesi | On the complexity of distributed network decomposition[END_REF], one can compute a (∆ + 1)-coloring (as well as a MIS) of arbitrary graphs in deterministic time O(n 1/ √ log n ). For graphs of maximum degree bounded by ∆, (∆ + 1)-coloring can be achieved in time O(∆ log n) (see [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF]). [START_REF] Cole | Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms[END_REF] described a PRAM algorithm that can be easily transformed into an algorithm working in the LOCAL model, computing a 3-coloring of oriented cycles in O(log * n) rounds. This bound is tight as proved by Linial [START_REF]Locality in distributed graph algorithms[END_REF] (see also [START_REF] Naor | A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring SIAM[END_REF] for a generalization to randomized algorithms). Similarly, [START_REF] Goldberg | Efficient parallel algorithms for (∆ + 1)-coloring and maximal independent set problems[END_REF] described a 3-coloring of oriented trees working in O(log * n)

rounds. The O(∆ 2 )-coloring algorithm in [START_REF]Locality in distributed graph algorithms[END_REF], working in O(log * n) rounds, can be easily converted into a (∆ + 1)-coloring algorithm working in O(∆ 2 + log * n) rounds, reaching the same complexity as the algorithm in [START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF]. [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] analyses what can be achieved in one round, and proves that no algorithm based on iterations of the application of a 1-round algorithm can achieve O(∆)-coloring in less than Ω(∆/ log 2 ∆ + log * n) rounds. On the other hand, [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] presents a (∆ + 1)-coloring algorithm working in O(∆ log ∆ + log * n) rounds, thus improving [START_REF] Awerbuch | Network Decomposition and Locality in Distributed Computation[END_REF][START_REF] Goldberg | Parallel symmetry-breaking in sparse graphs[END_REF][START_REF]Locality in distributed graph algorithms[END_REF]. Recently, the power of orienting the network was also demonstrated in terms of bit complexity in [START_REF] Kothapalli | Distributed coloring in O( √ log n) bit rounds[END_REF].

One can rephrase many recent results of the literature in the framework of advising schemes. For instance, a 0-round algorithm with maximum advice length O(log n) bits and average advice length O(log log n) is described in [START_REF] Cohen | Label-Guided Graph Exploration by a Finite Automaton[END_REF] for computing a spanning tree. It is also easy to extract an O(1)-round algorithm for spanning trees with maximum advice length 2 bits from the proof of the main result in [START_REF] Cohen | Labeling Schemes for Tree Representation[END_REF]. [START_REF] Fraigniaud | Local MST Computation with Short Advice[END_REF] have designed distributed algorithms with advice for computing minimum spanning trees (MST), and [START_REF] Nisse | Graph searching with advice[END_REF] have designed distributed algorithms with advice for solving the graph searching problem, a.k.a. the cops-and-robbers problem. Finally, [START_REF] Fraigniaud | Tree Exploration with an Oracle[END_REF] considers the competitive ratio of the exploration time of a robot unaware of the topology compared to a robot knowing the map of the graph.

Coloring cycles with advice

In order to prove the lower bounds listed in Section 1.1 on the size of advice needed for fast 3-coloring of all cycles, we prove the following result.

Theorem 2.1 Suppose that an oracle O informs at most q nodes in any n-node cycle.

Then the time of 3-coloring of n-node cycles using oracle O is Ω(log * (n/q)). This result holds even if the cycle is oriented, i.e., even if the nodes have a consistent notion of clockwise and counterclockwise directions.

Before proving Theorem 2.1, we make the following observation. A lower bound argument for a scenario in which an oracle is giving advice as a function of the instance cannot rely on arguments based solely on the existence of large sets of nodes without advice. Indeed, these specific large sets may not need any advice. A lower bound proof must combine arguments demonstrating the existence of large sets receiving no advice, with arguments about the difficulty of coloring these sets. The following example should help understanding this fact.

Example. Let K 2 be the graph consisting in two nodes linked by an edge. If nodes are labeled by IDs in {1, ..., 5}, then 3-coloring K 2 in zero rounds (i.e., without communication) is impossible. Indeed, for any function f mapping {1, ..., 5} to {0, 1, 2}, there is a pair x and y of distinct IDs such that f (x) = f (y), and thus there is an assignment of the IDs that causes the two neighboring nodes of K 2 to be mapped to the same color. Now, consider a cycle with five nodes, C 5 , with distinct node IDs in {1, ..., 5}.

If an oracle informs at most two nodes, then there are two adjacent nodes of C 5 that receive no information from the oracle. Using the fact that coloring K 2 in zero rounds is impossible, it may seem at a first glance that 3-coloring a cycle of length 5 with an oracle that informs at most 2 nodes is impossible because there is a copy of K 2 in C 5 that receives no advice, and coloring such a K 2 is impossible. There is a flaw in this reasoning because the 2 adjacent nodes that receive no information may actually be easy to color.

In fact, 3-coloring C 5 without communication, using an oracle that informs only 2 nodes is possible. Here is the algorithm:

1. Nodes receiving no advice are colored 0 or 1, depending on the parity of their IDs;

2. Nodes receiving advice are colored 2.

And here is the oracle strategy for assigning advices:

1. select two adjacent nodes x and y that have IDs with different parity;

2. let x ′ (resp., y ′ ) be the neighbors of x (resp., y) that is different from y (resp., x);

3. Nodes x ′ and y ′ are the two nodes that receive advice.

This algorithm with advice does 3-color the cycle. Indeed, (1) nodes x and y get different colors 0 and 1 because they have different parity; (2) nodes x ′ and y ′ get color 2; and (3)

the common neighbor z of x ′ and y ′ gets a color 0 or 1 depending on its parity.

The above example illustrates the fact that even if there exists a path P of length n/q in C n that receives no advice, this is not sufficient to conclude that Ω(log * (n/q)) rounds are required to 3-color C n . Indeed, 3-coloring this specific path P may actually be quite easy. We now give a complete proof of Theorem 2.1.

Proof. Recall the definition of the directed graph B t,n from [START_REF]Locality in distributed graph algorithms[END_REF]. Let s = 2t + 1 < n -1.

The nodes of the graph are sequences of length s of distinct integers from {1, . . . , n}.

Intuitively, node (x 1 , x 2 , . . . , x s ) of the graph B t,n represents the information acquired in time t by node x t+1 of a labeled directed cycle containing a segment (x 1 , x 2 , . . . , x s ).

Out-neighbors of node (x 1 , x 2 , . . . , x s ) are all nodes (x 2 , x 3 , . . . , x s , y), where y = x 1 . Note that the chromatic number χ(B t,n ) is a lower bound on the number of colors with which an n-node cycle may be colored distributively in time t. Thus, by restricting attention to 3-coloring algorithms, this yields a lower bound on the time of 3-coloring.

It was proved in [START_REF]Locality in distributed graph algorithms[END_REF] that χ(B t,n ) ≥ log (2t) n.

For any set X ⊆ {1, . . . , n} of size > s + 1, we define B t,n (X) as the subgraph of B t,n induced by all nodes (x 1 , x 2 , . . . , x s ) with x i ∈ X, for all 1 ≤ i ≤ s. The graph B t,n (X) is isomorphic to B t,|X| . To see why, just sort the elements of X in, say, increasing order, and consider the mapping ρ : X → {1, . . . , |X|} defined by ρ(x) = rank X (x). By extension, ρ induces an isomorphism ρ between B t,n (X) and B t,|X| , defined by ρ(x 1 , x 2 , . . . , x s ) = (ρ(x 1 ), ρ(x 2 ), . . . , ρ(x s )).

Fix an oracle O giving advice to all cycles of length n. Let q be the maximum number of nodes informed by oracle O in any of these cycles. Without loss of generality we may assume that the number of bits given to any node is not more than needed to code all directed labeled cycles of length n, i.e., ⌈log(n -1)!⌉. Consider a 3-coloring algorithm for cycles of length n using oracle O and running in time t. If t ≥ n/(2q) -1, we are done. Hence suppose that t < n/(2q) -1 which implies s < n/q.

We define the directed graph B t,n,O that will be crucial in our argument. Claim 2.1 For n/q sufficiently large, there exists a set X of size k = n q(s+1)

1/(s+1)
such that B t,n (X) is a subgraph of Bt,n,O .

We will establish an upper bound on the number of edges from the graph B t,n missing in Bt,n,O . This upper bound will allow us to prove that Bt,n,O contains a subgraph B t,n (X), for some set X of size k. Fix a directed labeled cycle of length n. When the oracle O informs a node of this cycle, exactly s + 1 of its segments (those containing the node) induce s + 1 edges in B t,n,O that are different than in B t,n,O ′ , where oracle O ′ differs from O by not informing this node. Moreover, these s + 1 edges in B t,n,O are outside Bt,n,O .

For a given cycle, at most q(s + 1) of the edges induced by all the n possible segments of the cycle are outside Bt,n,O . There are (n -1)! directed labeled cycles of length n. For a given edge e of B t,n not to appear in Bt,n,O , each of the (ns -1)! cycles that induces e in B t,n must not induce e in Bt,n,O . That is, the oracle must give advice to each of these many cycles in the segment corresponding to edge e. Let µ be the number of edges in B t,n that do not appear in Bt,n,O . Then

µ ≤ q(s + 1) • (n -1)! (n -s -1)! ≤ q • (s + 1) • n s .
Consider all graphs B t,n (X), for X of size k > s + 1. Every edge ((x 1 , x 2 , . . . , x s ), (x 2 , . . . , x s , x s+1 )) of B t,n belongs to at most n-s-1 k-s-1 such graphs B t,n (X), where all x i are in X. Thus there exist at most q • (s + 1) • n s • n-s-1 k-s-1 graphs B t,n (X), for X of size k, such that at least one of their edges does not appear in Bt,n,O . We will now prove that this number of graphs is strictly smaller than the total number n k of graphs B t,n (X), for X of a suitably chosen size k. Indeed,

n k n-s-1 k-s-1 = n(n -1) • • • (n -s) k(k -1) • • • (k -s) > n k s+1 . Let k = n q(s + 1) 1/(s+1)
.

Note that we have k > s + 1, for n/q sufficiently large. Hence

n k s+1 ≥ q • (s + 1) • n s .
Hence there exists a graph B t,n (X) all of whose edges appear in Bt,n,O . This proves Claim 2.1.

In view of Claim 2.1, the chromatic number of B t,n,O can be bounded as follows (for n/q sufficiently large):

χ(B t,n,O ) ≥ log (s-1) k = log (s-1) n q(s + 1) 1/(s+1)
. Since t is the running time of a 3-coloring algorithm for cycles of length n using oracle O, we have χ(B t,n,O ) ≤ 3, which implies log (s-1) n q(s+1) 1/(s+1) ≤ 3. In order to finish the argument, it is enough to prove that s ≥ 1 5 log * (n/q). Suppose not. Thus n/q ≥ 2 2 16 .

For such large n/q we have log n q(s + 1)

> log n q -log log * n q ≥ 1 2 log n q . Hence 1 s + 1 log n q(s + 1) > 1 2(s + 1) log n q ≥ 1 2 log * n q log n q ≥ log log n q .
This implies n q(s + 1)

1/(s+1)
> log n q , and 3 ≥ log (s-1) n q(s + 1)

1/(s+1) > log (s) n q .
Thus s ≥ log * n q -2, which contradicts the assumption s < 1 5 log * (n/q). Theorem 2.1 has several interesting consequences. The following corollary proves that transforming the 3-coloring problem into a locally solvable problem (in the sense of [START_REF] Naor | What can be computed locally?[END_REF])

essentially requires to give the solution to the nodes.

Corollary 2.1 Any distributed algorithm that produces a 3-coloring of all cycles of length n in constant time requires advice for Ω(n) nodes.

The next corollary proves that 3-coloring of cycles is information insensitive.

Corollary 2.2 Any distributed algorithm that produces a 3-coloring of all cycles of length n in time o(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

Coloring trees with advice

Theorem 2.1 concerning cycles has an interesting consequence concerning trees, that proves that 3-coloring is information insensitive in oriented trees. Recall that a tree is oriented if it is rooted, and every node is aware of which of its incident edges leads to its parent in the tree. If there exists an oracle O informing at most q nodes in any n-node oriented tree, and a 3-coloring algorithm A using O and working in t(n) rounds, then there exists an oracle O ′ informing at most q + 2 nodes in any n-node oriented cycle, and a 3-coloring algorithm A ′ using O ′ and working in t(n) + 1 rounds. O ′ picks arbitrarily two neighboring nodes x and y in the cycle. Assume that y is the neighbor of x in the counterclockwise direction. O ′ gives the advice (tail) to x, and the advice (t(n), root) to y. The ith node v in the cycle, counting counterclockwise from x, receives from O ′ the advice f (v i ) given by O to the node v i at distance i from the root of the oriented path P rooted at one of its two extremities, where f = O(P ). A ′ proceeds in t(n) + 1 rounds. During rounds 1 to t(n), A ′ simply executes A, for which nodes x and y just act as if they would be respectively the tail and the root of a directed path from x to y.

At round t(n) + 1 of A ′ , the root node y checks if its color is different from x. If not, it takes a color distinct from the colors if its two neighbors. This simple reduction enables to establish the following corollary of Theorem 2.1 proving that 3-coloring oriented trees is information insensitive.

Corollary 3.1 Suppose that an oracle O informs at most q nodes in any n-node oriented tree. Then the time of 3-coloring of n-node oriented trees using oracle O is Ω(log * (n/q)).

Thus in particular any distributed algorithm that produces a 3-coloring of all n-node oriented trees in time o(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

The main result of this section is a lower bound on the size of advice necessary for fast coloring of all n-node unoriented trees. In fact we will show that this bound holds already for the class of all unoriented complete d-regular trees. These are rooted trees T d,r such that each leaf is at distance r from the root, and each internal node (i.e., a node that is not a leaf) has degree d. Thus the root has d children, and all other internal nodes have d -1 children. It should be stressed that the notion of root and children is brought up only to facilitate the definition. From the point of view of nodes, the tree is not rooted (a node does not have information which neighbor is its parent). Proof. Fix d ≥ 37, t > 0, and r > 2t + 3. Consider any node v of the tree T d,r at distance at least t + 1 from all leaves. The number of nodes at distance at most t from v will be denoted by α(t). We have

α(t) = d• t-1 i=0 (d-1) i ≤ 2(d-1) t -1.
Consider an edge e of the tree T d,r whose both extremities are at distance at least t + 1 from all leaves. The subtree induced by the set of nodes at distance at most t from one of these extremities will be called the bow-tie of T d,r based on edge e, denoted by BT(e). The number of nodes in this bow-tie will be denoted by β(t). We have

β(t) = α(t) + 1 + (d -1) t ≤ 3(d -1) t .
Consider the tree T d,r with a labeling Φ of nodes and ports. Φ labels all nodes by distinct integers from {1, . . . , n}, where n = 1 + α(r), and labels all ports at internal nodes by integers from {1, . . . , d}. For any such labeled tree, consider its subtrees of the form N(v, t, Φ), where t is a positive integer and v is a node of T d,r at distance at least t + 1 from any leaf of T d,r . N(v, t, Φ) is defined as the labeled subtree of T d,r induced by all nodes at distance at most t from v. Note that if restrictions of labelings Φ and Φ ′ to the subtree of T d,r induced by all nodes at distance at most t from v are identical, then

N(v, t, Φ) = N(v, t, Φ ′ ).
Consider the following graph, denoted by G t (T d,r ). The nodes of G t (T d,r ) are all subtrees N(v, t, Φ) of T d,r for all possible nodes v, and all possible labelings Φ of nodes and ports of T d,r . Two nodes N(v, t, Φ) and N(v ′ , t, Φ ′ ) of G t (T d,r ) are adjacent, if and only if there exist two adjacent nodes w and w ′ in T d,r , and a labeling Ψ, such that

N(v, t, Φ) = N(w, t, Ψ) and N(v ′ , t, Φ ′ ) = N(w ′ , t, Ψ).
Note that the graph G t (T d,r ) is a subgraph of the t-neighborhood graph of T d,r , defined in [START_REF]Locality in distributed graph algorithms[END_REF]. Moreover, it follows from [START_REF]Locality in distributed graph algorithms[END_REF] that the chromatic number χ(G t (T d,r )) is a lower bound on the number of colors with which the tree T d,r may be colored distributively in time t, and that χ(G t (T d,r )) ≥ 1 2 √ d, if t < 2r/3. Also, for any set X ⊆ {1, . . . , n}, we define the graph G(X) as the subgraph of G t (T d,r ) induced by nodes with labels from the set X. For |X| = 1 + α(s), for some positive integer s ≤ r, the graph G(X) is isomorphic to G t (T d,s ). To see why, observe first that there are precisely 1+α(s) nodes in T d,s , labeled from 1 to 1 + α(s). To set the isomorphism between G(X) and G t (T d,s ), just sort the elements of X in, say, increasing order, and consider the mapping ρ : X → {1, . . . , |X|} defined by ρ(x) = rank X (x). By extension, ρ induces an isomorphism ρ between G(X)

and G t (T d,s ), defined by ρ(x 1 , x 2 , . . . , x s ) = (ρ(x 1 ), ρ(x 2 ), . . . , ρ(x s )).

Fix an oracle O giving advice to all n-node labeled trees T d,r . Let q be the maximum number of nodes informed by oracle O in any of these trees. Without loss of generality we may assume that the number of bits given to any node is not more than needed to code all n-node labeled trees T d,r . There are d α(r-1) port labelings of T d,r , and for each such labeling there are n! ways to label nodes. Hence the number of bits needed to code these trees is at most ⌈log(d α(r-1) n!)⌉. Consider a 3-coloring algorithm for n-node labeled trees T d,r using oracle O and running in time t. We define the following graph Similarly as before we will identify Gt,O (T d,r ) with this subgraph of G t (T d,r ).

Claim 3.1 Let ν(k) be the number of sets X of size k, such that the graph G(X) is not

a subgraph of Gt,O (T d,r ). Then ν(k) ≤ 2 • q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t) .
In order to prove Claim There are β(t) ways of choosing node b in the bow-tie B. For each such choice there are d α(r-1)-(β(t)-1) ways of fixing port numbers in T d,r because for every internal node other than the root the port leading to its parent has to be chosen and this has already been done for these nodes that appear in the bow-tie B. Finally for each such choice there are nβ(t) ! ways of labeling all nodes outside B. Hence in Case 1, there are

β(t) • d α(r-1)-β(t)+1 • n -β(t) ! labeled trees T d,r that contain B.
(d -1) t • d • r-(2t+3) i=0 (d -1) i • d α(r-1)-β(t) • n -β(t) ! labeled trees T d,r that contain B.
Consequently we have

λ =   β(t) • d α(r-1)-β(t)+1 + 2(d -1) t • d • r-(2t+3) i=0 (d -1) i • d α(r-1)-β(t)   • n -β(t) ! =   β(t) + 2(d -1) t • r-(2t+3) i=0 (d -1) i   d α(r-1)-β(t)+1 • n -β(t) ! ≥ 2(d -1) t • (d -1) r-(2t+3) • d α(r-1)-β(t) • n -β(t) ! .
≤ q • α(t + 1) • d α(r-1) • n! 2(d -1) t • (d -1) r-(2t+3) • d α(r-1)-β(t) • n -β(t) ! ≤ q • n! • d β(t) (d -1) r-(2t+3) • n -β(t) ! ≤ 2 • q • n! • d 4d t n • n -β(t) ! .
The last inequality follows from n ≤ (d -1) r and d β(t)+(2t+3) ≤ d 4d t . Consider all graphs G(X), for X of size k = α(⌊ such graphs G(X). Thus there exist

ν(k) ≤ 2 • q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t)
sets X of size k, such that the graph G(X) is not a subgraph of Gt,O (T d,r ). This proves Claim 3.1.

Suppose that ν(k) < n k . Then there exists a set X of size k for which G(X) is a subgraph of Gt,O (T d,r ). Since k = α(s) for s > 3t/2, it follows from [START_REF]Locality in distributed graph algorithms[END_REF] that the chromatic number of the graph G(X) (and thus also of the graph G t,O (T d,r )) is at least

1 2

√

d, which is larger than 3 for d ≥ 37. This contradicts the fact that we consider a 3coloring algorithm running in time Hence we may assume ν(k) ≥ n k . From Claim 3.1, this implies 2

• q • n! • d 4d t n • n -β(t) ! • n -β(t) k -β(t) ≥ n k
and hence the number q of informed nodes satisfies

q ≥ n • k -β(t) ! 2 • d 4d t • k! ≥ n 2 • d 4d t • k β(t) .
Since k = α(⌊ 3 2 t + 1⌋) ≤ d

Conclusion

We presented lower bounds on the amount of advice that has to be given to nodes of cycles and of trees in order to produce distributively a fast 3-coloring of these networks.

Although our lower bounds are very close to the obvious upper bound O(n), some interesting detailed questions concerning the trade-offs between the size of advice and the time of coloring remain open, even for cycles and trees. In particular, what is the minimum number of bits of advice to produce a 3-coloring of every n-node cycle or tree in a given time t = o(log * n)? More generally, what is the information sensitivity of coloring arbitrary graphs? For arbitrary graphs, it is natural to consider the maximum degree ∆ as a parameter, and seek distributed (∆ + 1)-coloring. It was proved in [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] that a (∆ + 1)-coloring can be produced in time O∆ log ∆ + log * n). What is the minimum number of bits of advice to produce a (∆ + 1)-coloring in time O(log * n)? And in constant time? We conjecture that for the former task O(n) bits of advice are sufficient, and for the latter Ω(n log ∆) bits of advice are needed. Finally, an intriguing question is whether the notion of oracle can be generalized to randomized algorithms. In particular, it would be interesting to generalized the lower bound in [START_REF] Naor | A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring SIAM[END_REF] to a context in which advices are given to nodes.

Figure 1 :

 1 Figure 1: Tradeoff between the execution time and the size of advice.

Theorem 3 . 1

 31 Fix d ≥ 37. Any 3-coloring algorithm working in time t for the class of n-node unoriented complete d-regular trees requires advice for at least n d d 2t nodes.

G

  t,O (T d,r ). Nodes of this graph are pairs of the form (N(v, t, Φ), f ), where N(v, t, Φ) is the tree defined above and f is a function from nodes of this tree into the set of binary strings of length at most ⌈log(d α(r-1) n!)⌉. Intuitively, the value f (w) is the advice given to node w of N(v, t, Φ) by the oracle, and the entire pair (N(v, t, Φ), f ) represents the total information acquired in time t by node v, including advice given to nodes of N(v, t, Φ) by the oracle. Edges of the graph G t,O (T d,r ) are defined as follows. There is an (undirected) edge between two nodes of G t,O (T d,r ) if these nodes are of the form (N(v, t, Φ), f ) and N(v ′ , t, Φ), f ′ ), for some labeling Φ, where v and v ′ are adjacent in T d,r and for all nodes w of N(v, t, Φ) and w ′ of N(v ′ , t, Φ), the values f (w) and f ′ (w ′ ) are advice strings given to nodes w and w ′ , respectively, by oracle O for the tree T d,r labeled by Φ. We will say that this edge of G t,O (T d,r ) is induced by the bow-tie BT({v, v ′ }) based on edge {v, v ′ } of the tree T d,r labeled by Φ.The chromatic number χ(G t,O (T d,r )) is a lower bound on the number of colors with which the tree T d,r may be colored distributively in time t, using oracle O. Similarly as in the case of the cycle, there may be "non-legitimate" nodes in G t,O (T d,r ) but they are isolated and thus do not affect the chromatic number.In order to establish a lower bound on the chromatic number of G t,O (T d,r ), it is sufficient to focus on the subgraph Gt,O (T d,r ) induced by the nodes (N(v, t, Φ), f ) with f being a function giving the empty string to all nodes. By definition, the graph Gt,O (T d,r ) is isomorphic to a subgraph of G t (T d,r ) and has the same number of nodes as G t (T d,r ).

  3.1, consider an edge of G t,O (T d,r ). Let λ be the number of labeled trees T d,r that contain a bow-tie B inducing this edge. Let b be the node of B closest to the root of T d,r . Consider two cases. Case 1. b is the root of T d,r .

Case 2 .

 2 b is not the root of T d,r . In this case b must be a leaf of B. The number of leaves of B is 2(d -1) t . For any choice of b there are d α(r-1)-β(t) ways of fixing the port number leading to the parent, for all internal nodes in T d,r other than the root and outside B. For any such choice there are d • r-(2t+3) i=0 (d -1) i ways of choosing the port numbers on the (unique) path from the root to b (index i corresponds to the distance between the root and node b). Finally, we have to consider again the nβ(t) ! ways of labeling all nodes outside B. Hence in Case 2, there are 2

7 2 t≥ n 2 • d 4d t • d 7 2Corollary 3 . 2 Corollary 3 . 3

 2273233 and β(t) ≤ 3(d -1) t , we haveq t•3(d-1) t ≥ n d d 2twhich completes the proof.Remark. By considering trees of a sufficiently large constant degree (instead of just degree d ≥ 37) we can generalize the above result to the case of c-coloring, for any constant c. Theorem 3.1 has several interesting consequences. The following corollary proves that lack of cycles does not help in coloring a network since transforming the 3-coloring problem in trees into a locally solvable problem essentially requires, as for cycles, to give the solution to the nodes. Any distributed algorithm that produces a 3-coloring of all n-node trees in constant time requires advice for Ω(n) nodes.The next corollary proves that reaching the O(log * n) bound in unoriented trees requires lot of advice. This should be contrasted with the fact that O(log * n) is the complexity of 3-coloring of oriented trees, without advice. Any distributed algorithm that produces a 3-coloring of all n-node unoriented trees in time O(log * n) requires advice for Ω(n/ log (k) n) nodes, for any constant k.

  The nodes of the graph are sequences ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )), where x i are distinct integers from {1, . . . , n} and α i are binary strings of length at most ⌈log(n -1)!⌉. Intuitively, node ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) represents the total information acquired in time t by node x t+1 of a labeled directed cycle containing a segment (x 1 , x 2 , . . . , x s ), including labels of nodes at distance at most t and advice given to them by the oracle. There , α 2 , . . . , α s , β to nodes x 1 , x 2 , . . . , x s , y, respectively. We will say that the segment (x 1 , x 2 , . . . , x s , y) of such a cycle induces this directed edge. Similarly as above, the chromatic number χ(B t,n,O ) is a lower bound on the number of colors with which the cycle may be colored distributively in time t, using oracle O. Note that a coloring algorithm using oracle O does not need to assign a color to all nodes ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) of B t,n,O . Indeed, it is possible that there is no cycle containing the segment (x 1 , x 2 , . . . , x s ), such that oracle O applied to this cycle gives advice α 1 , α 2 , . . . , α s to nodes x 1 , x 2 , . . . x s , respectively. However, by definition, such "non-legitimate" nodes are isolated in the graph B t,n,O and hence they do not affect its chromatic number.

exists a (directed) edge from node v = ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )) to a node w, if w = ((x 2 , α 2 ), . . . , (x s , α s ), (y, β)) and if there exists a labeled directed cycle of length n containing the segment (x 1 , x 2 , . . . , x s , y), such that oracle O applied to this cycle gives advice α 1

We will establish a lower bound on the chromatic number of B t,n,O , and then show how to deduce from it a lower bound on the time of 3-coloring with oracle O. To this end it is sufficient to focus on the subgraph Bt,n,O of B t,n,O induced by the nodes ((x 1 , α 1 ), (x 2 , α 2 ), . . . , (x s , α s )), with all α i being empty strings. By definition, the graph Bt,n,O is isomorphic to a subgraph of B t,n and has the same number of nodes as B t,n . By a slight abuse of notation we will identify Bt,n,O with this subgraph of B t,n .

Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.