Une preuve de la conjecture de Sabidussi sur les graphes idempotents pour le produit lexicographique

Pierre Ille
I2M, Aix-Marseille Université
/user/pierre.ille/

Date(s) : 10/02/2015   iCal
11 h 00 min - 12 h 00 min

Étant donnés des graphes G et H, le produit lexicographique G[H] de H par G est défini sur V(G)×V(H) de la façon suivante : pour tous (x,u),(y,v) ∈ V(G)×V(H), (x,u)(y,v) ∈ E(G[H]) si ( x≠y et xy ∈ E(G) ) ou ( x=y et uv ∈ E(H).
Un graphe G est idempotent pour le produit lexicographique (ou encore, est un point fixe du produit lexicographique) si G[G] est isomorphe à G. Pour éviter le cas trivial des graphes ayant au plus un sommet, on suppose qu’un graphe idempotent pour le produit lexicographique a au moins deux sommets et donc est infini. Nous construirons des graphes idempotents pour le produit lexicographique 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.
Considérons 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 permutations de V×V’ défini de la façon suivante. Étant donnée une permutation φ de V×V’, φ ∈ Γ≀Γ’ s’il existe g ∈ Γ et une fonction ε : V → Γ’ tels que pour tout (x,y) ∈ V×V’, on a :
φ((x,y))=(g(x),ε(x)(y)).

Le 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
Aut(G)≀Aut(H)≤Aut(G[H]).
En 1960, Sabidussi a conjecturé que si un graphe G est idempotent pour le produit lexicographique, alors
Aut(G)≀Aut(G)<Aut(G[G]).
Nous apportons une réponse positive à cette conjecture (voir [1]). La preuve est simple et concise ; elle est essentiellement basée sur l’associativité du produit lexicographique.

[1] P. Ille, A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product, Proceedings of the 7th French International Colloquium on Graph Theory (ICGT’05), Hyères (France), Discrete Math. 309 (2009), 3518–3522.

A proof of the Sabidussi conjecture on idempotent graphs for the lexicographic product

Given graphs G and H, the lexicographic product 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).
A 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 one vertex, we suppose that a graph idempotent for the lexicographic product has at least two vertices and therefore is infinite. We will build idempotent graphs for the lexicographic product by taking inspiration from the ordinal exponential, which allows us to reduce idempotence for the lexicographic product of graphs to idempotence for the lexicographic sum of total orders.
Consider sets V and V ‘and groups of permutations Γ of V and Γ’ of V ‘. The crown product Γ≀Γ’ of Γ’ by Γ is the group of permutations of V×V’ defined as follows. Given a permutation φ of V×V’, φ ∈ Γ≀Γ’ if there exists g ∈ Γ and a function ε: V → Γ’ such that for all (x,y) ∈ V×V’, we have : φ((x,y)) = (g(x),ε(x)(y)).

The group of automorphisms of a graph G is denoted Aut (G). Given the graphs G and H, it is easy to see that
Aut(G)≀Aut(H)≤Aut(G[H]).
In 1960, Sabidussi conjectured that if a graph G is idempotent for the lexicographic product, then
Aut(G)≀Aut(G)<Aut(G[G]).
We 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.

[1] P. Ille, A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product, Proceedings of the 7th French International Colloquium on Graph Theory (ICGT’05), Hyères (France), Discrete Math. 309 (2009), 3518–3522.

Catégories



Retour en haut