BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.2.3.1//EN TZID:Europe/Paris X-WR-TIMEZONE:Europe/Paris BEGIN:VEVENT UID:8170@i2m.univ-amu.fr DTSTART;TZID=Europe/Paris:20150210T110000 DTEND;TZID=Europe/Paris:20150210T120000 DTSTAMP:20241120T210053Z URL:https://www.i2m.univ-amu.fr/evenements/une-preuve-de-la-conjecture-de- sabidussi-sur-les-graphes-idempotents-pour-le-produit-lexicographique/ SUMMARY:Pierre Ille (I2M\, Aix-Marseille Université): Une preuve de la con jecture de Sabidussi sur les graphes idempotents pour le produit lexicogr aphique DESCRIPTION:Pierre Ille: Étant donnés des graphes G et H\, le produit lex icographique G[H] de H par G est défini sur V(G)×V(H) de la façon suiva nte : pour tous (x\,u)\,(y\,v) ∈ V(G)×V(H)\, (x\,u)(y\,v) ∈ E(G[H]) s i ( x≠y et xy ∈ E(G) ) ou ( x=y et uv ∈ E(H).\nUn graphe G est idemp otent pour le produit lexicographique (ou encore\, est un point fixe du pr oduit lexicographique) si G[G] est isomorphe à G. Pour éviter le cas tri vial des graphes ayant au plus un sommet\, on suppose qu’un graphe idemp otent pour le produit lexicographique a au moins deux sommets et donc est infini. Nous construirons des graphes idempotents pour le produit lexicogr aphique en nous inspirant de l’exponentielle ordinale\, ce qui permet de ramener l’idempotence pour le produit lexicographique des graphes à l ’idempotence pour la somme lexicographique des ordres totaux.\nConsidér ons des ensembles V et V' et des groupes de permutations Γ de V et Γ' de V'. Le produit en couronne Γ≀Γ' de Γ' par Γ est le groupe de permut ations de V×V' défini de la façon suivante. Étant donnée une permutat ion φ de V×V'\, φ ∈ Γ≀Γ' s'il existe g ∈ Γ et une fonction ε : V → Γ' tels que pour tout (x\,y) ∈ V×V'\, on a :\nφ((x\,y))=(g(x) \,ε(x)(y)).\nLe groupe d’automorphismes d’un graphe G est noté Aut(G ). Étant donnés des graphes G et H\, il est facile de voir que\nAut(G) ≀Aut(H)≤Aut(G[H]).\nEn 1960\, Sabidussi a conjecturé que si un graphe G est idempotent pour le produit lexicographique\, alors\nAut(G)≀Aut(G) <\;Aut(G[G]).\nNous apportons une réponse positive à cette conjecture (voir [1]). La preuve est simple et concise \; elle est essentiellement ba sée sur l’associativité du produit lexicographique.\n[1] P. Ille\, A p roof of a conjecture of Sabidussi on graphs idempotent under the lexicogra phic product\, Proceedings of the 7th French International Colloquium on G raph Theory (ICGT’05)\, Hyères (France)\, Discrete Math. 309 (2009)\, 3 518–3522.\nA proof of the Sabidussi conjecture on idempotent graphs for the lexicographic product \nGiven graphs G and H\, the lexicographic produ ct G[H] of H by G is defined on V(G)×V(H) as follows: for all (x\,u)\, (y \,v) ∈ V(G) × V(H)\, (x\,u) (y\,v) ∈ E(G[H]) if (x≠y and xy ∈ E(G )) or (x=y and uv ∈ E(H).\nA graph G is idempotent for the lexicographic product (or again\, is a fixed point of the lexicographic product) if G[G ] is isomorphic to G. To avoid the trivial case of graphs having at most o ne vertex\, we suppose that a graph idempotent for the lexicographic produ ct has at least two vertices and therefore is infinite. We will build idem potent graphs for the lexicographic product by taking inspiration from the ordinal exponential\, which allows us to reduce idempotence for the lexic ographic product of graphs to idempotence for the lexicographic sum of tot al orders.\nConsider sets V and V 'and groups of permutations Γ of V and Γ' of V '. The crown product Γ≀Γ' of Γ' by Γ is the group of permut ations of V×V' defined as follows. Given a permutation φ of V×V'\, φ ∈ Γ≀Γ' if there exists g ∈ Γ and a function ε: V → Γ' such th at for all (x\,y) ∈ V×V'\, we have : φ((x\,y)) = (g(x)\,ε(x)(y)). \nT he group of automorphisms of a graph G is denoted Aut (G). Given the graph s G and H\, it is easy to see that\nAut(G)≀Aut(H)≤Aut(G[H]).\nIn 1960\ , Sabidussi conjectured that if a graph G is idempotent for the lexicograp hic product\, then\nAut(G)≀Aut(G)<\;Aut(G[G]).\nWe provide a positive answer to this conjecture (see [1]). The proof is simple and concise\; it is essentially based on the associativity of the lexicographic product.\n[ 1] P. Ille\, A proof of a conjecture of Sabidussi on graphs idempotent und er the lexicographic product\, Proceedings of the 7th French International Colloquium on Graph Theory (ICGT’05)\, Hyères (France)\, Discrete Math . 309 (2009)\, 3518–3522.\n ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2 020/01/Pierre_Ille-new.jpg CATEGORIES:Séminaire,Ernest END:VEVENT BEGIN:VTIMEZONE TZID:Europe/Paris X-LIC-LOCATION:Europe/Paris BEGIN:STANDARD DTSTART:20141026T020000 TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET END:STANDARD END:VTIMEZONE END:VCALENDAR