Graphes de Coxeter

[fderwelt]

Bonjour,

J'ai un ch'tit problème, technique, mais j'aimerais avoir une soluce explicite.

Il s'agit de trouver tous les graphes qui obéissent aux règles suivantes:

(0) le graphe est connexe (normalement ça va sans dire, mais ça va mieux en le disant).

(1) chaque sommet est affecté d'un "poids" entier positif (entier naturel, quoi, si vous préférez).

(2) les connexions entre sommets sont simples, doubles, ou triples, avec les règles:

A--B : le poids de B est le même que celui de A;
A==B : le poids de B est le double de celui de A (ou le contraire, celui de A double de celui de B);
A==B: le poids de B est le triple de celui de A (ou le contraire, voir ci-dessus).

Alors voilà: je cherche à énumérer tous (à isomorphisme près, évidemment) les graphes avec un nombre donné de sommets. Oh bien sûr, j'ai écrit un programme qui fait cette énumération récursivement, et qui ensuite élimine les isomorphes par une méthode que la morale réprouve, mais il ne marche (en temps raisonnable s'entend) que jusqu'à la dimension 6 (déjà 40 heures de calcul). Or il me faut cette énumération jusqu'à 32 sommets, théorie des cordes oblige. Aliors, PLEASE HELP!!!

Si j'ai intitulé ce fil "Graphes de Coxeter", ce n'est pas par hasard. Les graphes qui m'intéressent sont ceux qui dérivent des graphes de Coxeter A_n, B_n, C_n, (dual de B_n) et D_n, et dans une moindre mesure, E₆, E₇, E₈, F₄ et G₂. Et aussi, dans une encore moindre mesure, les hyperboliques compacts T_pqr.

Je sais aussi que tous les graphes que je cherche se déduisent d'une des formes "canoniques" de Coxeter citées ci-avant, par des opérateurs de conjugaison que je n'écrirai pas ici parce que TeX me fait ch... Mais en gros, l'opérateur (je disais quoi sur TeX au fait?) permute les connexions (ik) et (jk), en bidouillant la connexion (ij) d'une manière très naturelle mais enquiquinante à expliquer. C'est d'ailleurs comme ça que j'ai écrit mon premier programme d'énumération.

Toute idée géniale sera la bienvenue, et sera citée nommément dans ma biographie, quand j'aurai enfin été reconnu comme le plus grand mathélaticien de tous les temps (au passage, merci à azt, ça fait plaisir de voir qu'il y en a qui suivent...)

-- françois
-----

[invite986312212]

il manque une contrainte: il faut borner les poids.

[homotopie]

Un programme libre de téléchargement est dispo (je pense qu'il doit répondre à ta question, je te laisse vérifier) :
http://math.univ-lyon1.fr/~ducloux/c...oxeter3_f.html

[fderwelt]

il manque une contrainte: il faut borner les poids.

Bonjopur et merci,

J'aimerais bien... Il est "évident" intuitivement que les poids sont bornés (ne serait-ce que parce que les sommets sont en nombre fini, ce que je n'avais pas précisé), mais à part les bornes évidentes du style 2ⁿ ou 3ⁿ, rien de très évident ne s'impose.

-- françois

[A voir en vidéo sur Futura]

[fderwelt]

Bonjour et merci à homotopie!

Ce site ne m'aide pas vraiment pour le problème posé, mais me sera très très très utile pour de nombreux calculs que je m'apprêtais à me palucher sur les groupes de Coxeter. Si tout le monde publiait ses pages de calculs, ça éviterait bien des redites et des redécouvertes de la roue (qui, d'ailleurs, sont souvent bénéfiques, mais c'est un autre sujet).

-- françois

[invite986312212]

Bonjopur et merci,

J'aimerais bien... Il est "évident" intuitivement que les poids sont bornés (ne serait-ce que parce que les sommets sont en nombre fini, ce que je n'avais pas précisé), mais à part les bornes évidentes du style 2ⁿ ou 3ⁿ, rien de très évident ne s'impose.

-- françois

c'est moi qui dois l'être, mais je ne vois pas pourquoi tes poids seraient bornés. Même le graphe à 1 sommet, tu peux lui affecter n'importe quel poids entier positif (?) ou bien tu quotientes par la somme des poids?

[fderwelt]

Bonjour,

c'est moi qui dois l'être, mais je ne vois pas pourquoi tes poids seraient bornés. Même le graphe à 1 sommet, tu peux lui affecter n'importe quel poids entier positif (?) ou bien tu quotientes par la somme des poids?

Tu as évidemment raison. Je suis trop plongé dans le truc, il y a tout un tas d'hypothèses que je prends en compte implicitement. C'est sûr que ce n'est pas terrible pour communiquer...

En particulier, on peut supposer les poids premiers entre eux (dans leur ensemble). Mais il y a pas mal d'autres possibilités pour limiter la combinatoire. Avant de dire des bêtises, je mets ça au net, et on en reparlera quand le problème sera proprement spécifié.

Parce que là, en l'état, c'est sûr qu'on peut faire n'importe quoi.

-- françois