D IAGRAMMES A LBERT B URRONI Algèbres graphiques (suites : Les bidules) Diagrammes, tome 7 (1982), exp. no 1, p. B1-B8 © Université Paris 7, UER math., 1982, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Diagrammes, Vol. 7 9 1982. ALGEBRES GRAPHIQUES (suites les bidules.) par Albert Burroni à Yves Cantelaube Cet article est la première partie d , un travail qui étudie une définition interne des algèbres graphiques et ~ au delà - des algèbres en général. 1. Algèbres graphiques internes. ( . La catégorie Grph = Ens >. ^ ) est cartésienne fermée; on peut donc y définir des objets algébriques de façon interne. On appellera algèbre graphique interne la donnée d f un graphe G muni d'un système (Q,E) de lois et d'équations dans le sens suivants une loi interne sur G est un homomorphisD Df me de graphes de la forme a s G > G , où D, D f sont D Df deux graphes et G , G des exponentielles internes i. e. telles que B 2 H >GD H x D > G pour tous graphes H et G , A partir-d'une famille lois internes sur n de G , on peut en définir de nouvelles s les lois dérivées. On appellera ainsi toutes les lois de O et f toutes celles qu on peut définir inductivement à partir des deux règles suivantes s (i) Pour tout homomorphisme de graphes la projection G sG (ii) La composée * ^ G \i \ D \% G vees D > GD" sG D et > D , est une loi dérivée; f > G fs Df de deux lois déri- 1 D,f p,s G > G est une loi dé- rivée. Une équation interne sur fî est une égalité de la forme \ = X' , où E \, X's G — > G sont deux lois dérivées. est alors une famille d'équations internes sur D . Cette définition est une imitation formelle de ma définition des algèbres graphiques dans (1) et (2). Par opposition, on les appellera ici algèbres graphiques externes. La seule différence dans les deux définitions est que dans le dernier cas les lois et les équations sont externes, i. e. ce sont des applications de la forme as G(D) > G(D f ), où D—> G G(D) est l'ensemble des homomorphismes de graphes (donc G(D) s G D ( < 3 0 , où «CT3^ S X eSt le g r a p h e fi ~ nal). Comme je le montrerai dans la suite de cet article, bien que les règles (i) et (ii) soient en apparence insuffisantes pour décrire toutes les lois qui mériteraient d'être appelées "lois dérivées" et bien que dans le cas interne on pourrait imaginer une définition encore plus "interne" (par exemple et E O pourraient être des données graphiques et pas seulement ensemblistes), la définition ci-dessus suffit pour décrire tout ce qui mérite d'être appelé "algèbres graphiques". B 3 Proposition. Les algèbres graphiques internes peuvent toujours être définies comme algèbres graphiques externes. Preuve. Tout simplement parce qu'une loi graphique interne „D D' as G »> G , qui est un homomorphisme de graphes, est définie par deux lois externes s G(D x (. > .) ) — Fifo) -> G(Df x ( . 5> . ) ) * G(D x ( . ) ) -> f G(D x ( . ) ) Obfo) e t l e s équations externes? Obfo) a = a F i f o ) Obfo) b = b F i f o ) G(D x ( . ) ) = GD( . ) = Ob(GD) , et puisque G(D x ( . a , b > . ) ) = GD( . > . ) = F1(G D ) et où l e s sont des projections externes. Les équations internes se ramènent alors évidemment à des équations externes, // La réciproque de la proposition précédente n'est pas vraie en général. Par exemple, le lecteur peut essayer de définir de façon interne une loi de la forme a : G(.- -> . ) -> G( . ) Par la suite, je donnerai une caractérisation du cas interne. 2. Bigraphes. G C.op Soit es = Ens une catégorie de préfaisceaux sur une petite catégorie C . On appelle bidule de € un couple 6 = (0*9,,) de foncteurs adjoints? 9 -i 0 J : £ > € J 6 d g d ^- B 4 On adoptera les notations suivantes; A x 0 = 6 (A) , B 6 = e.(B) g a de sorte qu'on écrit l'équivalence d'adjonction sous la formes Axe —> B ->B9 et on appelle B une puissance généralisée. Ces notations seront prolongées aux morphismes. Les bidules forment les objets d'une catégorie B i d ( Ë ) , les morphismes entre bidules éteint définis par des transformations naturelles. C°P x C é* Proposition. On a Bid( £ ) Ci Ens bidules de Preuve. € . Autrement dit, les seront identifiés à des "profoncteurs" 0s C -—-> C• 0 est déterminé à isomorphisme près par 0 , lequel o P est un foncteur qui commute aux lim* etC °donc déterminé par sa restriction 0 j n % C • • > Ens , où C est idengI C c op tifié à son image dans Ens par le plongement de Yoneda. // En particulier, on as Bid(Ens) ^ Bid(Grph) Oi Ens Grph Donc les puissances généralisées dans Ens ~*** coïncident avec les puissances ordinaires. Par contre les bidules de Grph en fait, des bigraphes sont, (i. e. des cographes dans les graphes ou encore des graphes doubles puisque (. ^*) 1^ (. -^.) ). Les bigraphes décrivent une quantité de constructions remarquables sur les graphes. En voici quelques unes; 1) Pour tout graphe D on définit le bigraphe D ;D x ( . ) ^ D x ( induit par le bigraphe "unité" ( . ) ^ ( . Alors, on retrouve les puissances internes s G £, G g. ) > • ). % B 5 2) De même, pour D s D sances externes? au graphe ^ D , on retrouve les puis- G Oi G(D) , en identifiant tout ensemble E . IdE ^ ,- ^ Id E appelé graphe discretg 3) Soit ( .—^ . —^. . ## ^ . ) i e graphe formé de n flèches consécutives pour n entier (et réduit à ( . ) si n = 0 ), alors on a le;bigraphe s • * - n ; ( • a y _ 57 ) ( . - ^ . _ _ ^ . . . . . _ ^ , ) # où lfunique objet de ( . ) est envoyé sur le premier objet (resp. le dernier objet) de (._> . _^ e ..." . _ > . ) par a (resp. b )$n n u alors, on as G 0? H G est le graphe des chemins de longueur n dans G , puisque n 0b( H G ) = Ob(G) n Fl( H G ) = G ( . _ > . ^ _ > . )« A) On peut prolonger la définition précédente pour tout n Ç Z en inversant a et b dans le cas n < 0 s w < • > zz:><• ..) b (si n > 0 ) $ 1. en particuliers G "" ûf G op 5 a 5) Pour Si ( . ) * ( .<— ^>. ) , où a et b b envoient respectivement l'unique objet de ( • ) sur le premier et le troisième objet de ( . <£ = . ^. Span (G) ) , on a B 6 6 ) Pour €. s ( ) ^, (. . ^ . ) , on a G£ G/Ob(G) = obtenu en identifiant tous les objets de G$ 7) Pour ^>(*) » fs ( ) Ob(Gf) = 1 , G est le 6 ra P he t e l Q u e Fl(Gf) = Ob(G) | Pour chacune de ces constructions, on a évidemment une construction duales de l'exemple 5) G* > G x 0 (par exemple, le dual donne la "subdivision barycentrique" d'un graphe). Ces constructions sont d'ailleurs faciles à "visualiseras - pour tout bigraphe 0s Q ~% 0- , on as 0 + G est le graphe tel que F1(G0) = G(0X) , 0 Ob(G ) = G(0 ) et + G x 0 est une somme amalgamée de copies de 0, , indexée par un diagramme dont le type est donné par la subdivision barycentrique de 0n et G . 3. Algèbres graphiques internes généralisées. En utilisant les puissances généralisées, on peut étendre maintenant la définition du §1. Une algèbre graphique interne généralisée est définie comme pour les algèbres graphiques 0 0f internes mais les lois y sont de la forme as G •—>G où 0,01 , sont des bigraphes et les projections sont induites par des morphismes 0' ^>0 de bigraphes. Théorème. Les algèbres graphiques externes peuvent être définies comme algèbres graphiques internes généralisées et réciproquement. B 7 Preuve. La première affirmation résulte de ce qui a été observé dans l'exemple 2) du §2. La réciproque s'obtient en ramenant toute loi interne généralisée a s Ge •»G e1 a deux lois externes, comme pour les algèbres internes; GCep ^>G(ep FKcO ^ y •> G(e^) G(G 0 ) 0b(o0 et deux équations externes, où 0'; 0' 0 ^ ih 0s 0 et 0*. sont deux bigraphes. // Terminons par quelques remarques s 1) J'utilise les expressions "interne" et "externe" d'une manière informelle en leur laissant le caractère ouvert qu'elles ont dans la littérature. Ici, cela dépend des constructions qu'on considère comme internes à la catégorie Grph , en ad- mettant que cette catégorie est seulement un topos ou bien qu'elle est munie de données plus riches, comme par exemple 2 l'opérateur Gt—>& G • Ainsi, la donnée d'une structure de catégorie sur un objet G de Grph peut être considérée comme interne en la définissant comme une "monade" avec les "lois"s 2 0 H G -> G C' et conduit à unifier de nom- breuses constructions, (à suivre ...) Bibliographie. (1) A. Burroni, Algèbres Graphiques, Cah. de Top. et Géom. Diff., XXII-3 (1981). (2) A. Burroni, Conférence de Cambridge, Juillet 1981, manuscript.