Recherche matrice désespérément

bisam
bisam
dans Logiciels pour les mathématiques
Bonsoir,

Suite à un exercice d'algèbre trouvé dans la RMS, je cherche des matrices vérifiant des conditions très particulières.
Les conditions sont les suivantes :
  1. $A$ est une matrice carrée de taille $n$, symétrique, et n'ayant que des $0$ et des $1$ comme coefficients
  2. la trace de $A$ est nulle, ce qui implique qu'il n'y a que des $0$ sur la diagonale,
  3. $A^2+A=(p-1)I_n + J$ où $p\in\N$, $I_n$ est la matrice unité de taille $n$ et $J$ la matrice carrée de taille $n$ ne contenant que des $1$.

On peut alors démontrer que si $U$ est le vecteur colonne ne contenant que des $1$ alors $AU=pU$, ce qui a notamment pour conséquence que $n$ et $p$ sont liés par la relation $n=p^2+1$ (c'est cadeau).

Par ailleurs, il y a un lien évident avec les matrices d'adjacence d'un graphe non orienté ni valué.
Plus précisément, la relation $AU=pU$ implique que chaque sommet du graphe est exactement de degré $p$ et la 3ème condition implique que pour chaque couple de sommets distincts, soit ils sont voisins, soit il existe exactement 1 chemin de longueur 2 les reliant.

Avec ces deux dernières informations, par symétrie des rôles des sommets du graphe, on peut fortement limiter les recherches et on arrive à trouver des solutions pour le cas $p=3$ (et donc $n=10$). On arrive même à prouver par une recherche exhaustive (mais maligne) que toutes les solutions donnent des graphes isomorphes dans ce cas.
Les cas $p=0$ et $p=1$ sont triviaux, et le cas $p=2$ est relativement facile.

Il reste à traiter les cas où $p\geq 4$... et là, ça se corse.
Il faut encore plus raisonner pour éliminer drastiquement le champ des possibles car une recherche exhaustive dépasse largement les capacités de nos pauvres ordinateurs.

Je pense avoir réussi à prouver par une recherche maligne qu'il n'y a aucune solution pour $p=4$ (mais je suis loin d'avoir prouvé réellement que mon algorithme et mes restrictions sont corrects) et je conjecture que c'est le cas pour toute valeur de $p$ plus grande.

Ma question est donc : "Ai-je raison ?"

Saurez-vous trouver une telle matrice $A$ pour $p=4$ (et donc $n=17$) et prouver que j'ai tort... ou au contraire prouver que j'ai raison par l'exhaustion ou par le raisonnement ?

J'avoue qu'un raisonnement prouvant que les seuls cas possibles sont $p\in\{0,1,2,3\}$ me ravirait.


PS : Si vous êtes sages, je posterai une photo d'un graphe qui convient pour $p=3$... et peut-être même quelques bouts de Python.

Réponses

  • Chaurien
    Chaurien
    J'ai vu des choses analogues dans Ryser, mais ce n'est pas exactement ça.
    Quelle est la référence de l'exo dans la RMS ? ENS ?
    Bonne soirée.
    Fr. Ch.
  • bisam
    bisam
    @ Chaurien : exercices 195 (X MP) et 664 (Centrale MP), RMS n°126
    Celui de Centrale est plein de petites fautes de retranscription... et il est très exigeant en demandant de montrer que $p$ peut prendre 5 valeurs différentes.

    Je m'aperçois qu'il a une astérisque... donc une correction a dû être publiée cette année. Mais je n'ai pas le numéro en question.
  • claude quitté
    claude quitté
    @bisam
    Peux tu lire les quelques lignes avant l'introduction in http://www.renyi.hu/~p_erdos/1980-14.pdf ? Si je comprends bien, il n'existe que 4 graphes de diamètre 2, de degré maximum $d$, ayant $d^2 + 1$ sommets. Je crois comprendre qu'un tel graphe est régulier. Mot-clé : Moore graphs.

    Regarde aussi le début de la section 3.1, page 8 in http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS14/pdf, en particulier (1) en y faisant $D = 2$ (le diamètre) : on obtient la borne de Moore $n_{\Delta,2} \le 1 + \Delta^2$ ; note : $\Delta$ est le degré maximum et $n_{\Delta,2}$ le nombre de sommets. Je crois comprendre que les 4 graphes de Moore pour lesquels la borne est atteinte ont pour degré $2, 3, 7, 57$. A cette page 8, dernière ligne, on voit l'égalité $A^2 + A - (\Delta-1)I = J$, qui en principe doit te rappeler quelque chose. Avec une piste en haut de la page 9 et une référence bibliographique. Pour le degré 7, le graphe obtenu à $7^2 + 1 = 50$ sommets est le graphe de Hoffman-Singleton.

    Vérifie tout ce que je dis, je n'y connais rien.
  • claude quitté
    claude quitté
    @bisam
    J'ai pensé que cela te ferait chaud au coeur de voir un peu des choses du graphe de Hoffman-Singleton (le graphe de Moore de degré 7, a $7^2 + 1= 50$ sommets). Tu en trouveras des schémas sur le net (est ce que le graphe régulier de degré 3 que tu nous a promis ne va pas faire un peu pâlichon à côté ?). Ici, j'ai suivi la construction donnée dans le théorème 2.1 de https://link.springer.com/content/pdf/10.1023/A:1025136524481.pdf. L'ensemble des sommets est $\Z/2\Z \times \Z/5\Z \times \Z/5\Z$ ; en ce qui concerne les arêtes, c'est un tantinet plus compliqué, cf ci-dessous :

     
    > Z2 := ResidueClassRing(2) ;
> Z5 := ResidueClassRing(5) ;
> V := CartesianProduct(<Z2, Z5, Z5>) ;
> 
> //  (0,x,y) --- (0,x,y')  ssi y-y' = +-1
> E1 := {@ {<Z2!0,x,y1>, <Z2!0,x,y2>} : x in Z5, y1,y2 in Z5 | y2-y1 in {-1,1} @} ;
> //  (1,x,y) --- (1,x,y')  ssi y-y' = +-2
> E2 := {@ {<Z2!1,x,y1>, <Z2!1,x,y2>} : x in Z5, y1,y2 in Z5 | y2-y1 in {-2,2} @} ;
> //  (0,x1,y) --- (1,x,xx1+y)
> E3 := {@ {<Z2!0,x1,y>, <Z2!1,x,x*x1+y>} : x,x1,y in Z5 @} ;
> 
> // Hoffman-Singleton Graph
> HS := Graph < {@ v : v in V @} | E1 join E2 join E3 > ;
> HS ;
Graph
Vertex  Neighbours

<0, 0, 0>       <0, 0, 1> <0, 0, 4> <1, 0, 0> <1, 1, 0> <1, 2, 0> <1, 3, 0> <1, 4, 0> ;
<0, 0, 1>       <0, 0, 0> <0, 0, 2> <1, 0, 1> <1, 1, 1> <1, 2, 1> <1, 3, 1> <1, 4, 1> ;
<0, 0, 2>       <0, 0, 1> <0, 0, 3> <1, 0, 2> <1, 1, 2> <1, 2, 2> <1, 3, 2> <1, 4, 2> ;
<0, 0, 3>       <0, 0, 2> <0, 0, 4> <1, 0, 3> <1, 1, 3> <1, 2, 3> <1, 3, 3> <1, 4, 3> ;
<0, 0, 4>       <0, 0, 0> <0, 0, 3> <1, 0, 4> <1, 1, 4> <1, 2, 4> <1, 3, 4> <1, 4, 4> ;
<0, 1, 0>       <0, 1, 1> <0, 1, 4> <1, 0, 0> <1, 1, 1> <1, 2, 2> <1, 3, 3> <1, 4, 4> ;
<0, 1, 1>       <0, 1, 0> <0, 1, 2> <1, 0, 1> <1, 1, 2> <1, 2, 3> <1, 3, 4> <1, 4, 0> ;
<0, 1, 2>       <0, 1, 1> <0, 1, 3> <1, 0, 2> <1, 1, 3> <1, 2, 4> <1, 3, 0> <1, 4, 1> ;
<0, 1, 3>       <0, 1, 2> <0, 1, 4> <1, 0, 3> <1, 1, 4> <1, 2, 0> <1, 3, 1> <1, 4, 2> ;
<0, 1, 4>       <0, 1, 0> <0, 1, 3> <1, 0, 4> <1, 1, 0> <1, 2, 1> <1, 3, 2> <1, 4, 3> ;
<0, 2, 0>       <0, 2, 1> <0, 2, 4> <1, 0, 0> <1, 1, 2> <1, 2, 4> <1, 3, 1> <1, 4, 3> ;
<0, 2, 1>       <0, 2, 0> <0, 2, 2> <1, 0, 1> <1, 1, 3> <1, 2, 0> <1, 3, 2> <1, 4, 4> ;
<0, 2, 2>       <0, 2, 1> <0, 2, 3> <1, 0, 2> <1, 1, 4> <1, 2, 1> <1, 3, 3> <1, 4, 0> ;
<0, 2, 3>       <0, 2, 2> <0, 2, 4> <1, 0, 3> <1, 1, 0> <1, 2, 2> <1, 3, 4> <1, 4, 1> ;
<0, 2, 4>       <0, 2, 0> <0, 2, 3> <1, 0, 4> <1, 1, 1> <1, 2, 3> <1, 3, 0> <1, 4, 2> ;
<0, 3, 0>       <0, 3, 1> <0, 3, 4> <1, 0, 0> <1, 1, 3> <1, 2, 1> <1, 3, 4> <1, 4, 2> ;
<0, 3, 1>       <0, 3, 0> <0, 3, 2> <1, 0, 1> <1, 1, 4> <1, 2, 2> <1, 3, 0> <1, 4, 3> ;
<0, 3, 2>       <0, 3, 1> <0, 3, 3> <1, 0, 2> <1, 1, 0> <1, 2, 3> <1, 3, 1> <1, 4, 4> ;
<0, 3, 3>       <0, 3, 2> <0, 3, 4> <1, 0, 3> <1, 1, 1> <1, 2, 4> <1, 3, 2> <1, 4, 0> ;
<0, 3, 4>       <0, 3, 0> <0, 3, 3> <1, 0, 4> <1, 1, 2> <1, 2, 0> <1, 3, 3> <1, 4, 1> ;
<0, 4, 0>       <0, 4, 1> <0, 4, 4> <1, 0, 0> <1, 1, 4> <1, 2, 3> <1, 3, 2> <1, 4, 1> ;
<0, 4, 1>       <0, 4, 0> <0, 4, 2> <1, 0, 1> <1, 1, 0> <1, 2, 4> <1, 3, 3> <1, 4, 2> ;
<0, 4, 2>       <0, 4, 1> <0, 4, 3> <1, 0, 2> <1, 1, 1> <1, 2, 0> <1, 3, 4> <1, 4, 3> ;
<0, 4, 3>       <0, 4, 2> <0, 4, 4> <1, 0, 3> <1, 1, 2> <1, 2, 1> <1, 3, 0> <1, 4, 4> ;
<0, 4, 4>       <0, 4, 0> <0, 4, 3> <1, 0, 4> <1, 1, 3> <1, 2, 2> <1, 3, 1> <1, 4, 0> ;
<1, 0, 0>       <0, 0, 0> <0, 1, 0> <0, 2, 0> <0, 3, 0> <0, 4, 0> <1, 0, 2> <1, 0, 3> ;
<1, 0, 1>       <0, 0, 1> <0, 1, 1> <0, 2, 1> <0, 3, 1> <0, 4, 1> <1, 0, 3> <1, 0, 4> ;
<1, 0, 2>       <0, 0, 2> <0, 1, 2> <0, 2, 2> <0, 3, 2> <0, 4, 2> <1, 0, 0> <1, 0, 4> ;
<1, 0, 3>       <0, 0, 3> <0, 1, 3> <0, 2, 3> <0, 3, 3> <0, 4, 3> <1, 0, 0> <1, 0, 1> ;
<1, 0, 4>       <0, 0, 4> <0, 1, 4> <0, 2, 4> <0, 3, 4> <0, 4, 4> <1, 0, 1> <1, 0, 2> ;
<1, 1, 0>       <0, 0, 0> <0, 1, 4> <0, 2, 3> <0, 3, 2> <0, 4, 1> <1, 1, 2> <1, 1, 3> ;
<1, 1, 1>       <0, 0, 1> <0, 1, 0> <0, 2, 4> <0, 3, 3> <0, 4, 2> <1, 1, 3> <1, 1, 4> ;
<1, 1, 2>       <0, 0, 2> <0, 1, 1> <0, 2, 0> <0, 3, 4> <0, 4, 3> <1, 1, 0> <1, 1, 4> ;
<1, 1, 3>       <0, 0, 3> <0, 1, 2> <0, 2, 1> <0, 3, 0> <0, 4, 4> <1, 1, 0> <1, 1, 1> ;
<1, 1, 4>       <0, 0, 4> <0, 1, 3> <0, 2, 2> <0, 3, 1> <0, 4, 0> <1, 1, 1> <1, 1, 2> ;
<1, 2, 0>       <0, 0, 0> <0, 1, 3> <0, 2, 1> <0, 3, 4> <0, 4, 2> <1, 2, 2> <1, 2, 3> ;
<1, 2, 1>       <0, 0, 1> <0, 1, 4> <0, 2, 2> <0, 3, 0> <0, 4, 3> <1, 2, 3> <1, 2, 4> ;
<1, 2, 2>       <0, 0, 2> <0, 1, 0> <0, 2, 3> <0, 3, 1> <0, 4, 4> <1, 2, 0> <1, 2, 4> ;
<1, 2, 3>       <0, 0, 3> <0, 1, 1> <0, 2, 4> <0, 3, 2> <0, 4, 0> <1, 2, 0> <1, 2, 1> ;
<1, 2, 4>       <0, 0, 4> <0, 1, 2> <0, 2, 0> <0, 3, 3> <0, 4, 1> <1, 2, 1> <1, 2, 2> ;
<1, 3, 0>       <0, 0, 0> <0, 1, 2> <0, 2, 4> <0, 3, 1> <0, 4, 3> <1, 3, 2> <1, 3, 3> ;
<1, 3, 1>       <0, 0, 1> <0, 1, 3> <0, 2, 0> <0, 3, 2> <0, 4, 4> <1, 3, 3> <1, 3, 4> ;
<1, 3, 2>       <0, 0, 2> <0, 1, 4> <0, 2, 1> <0, 3, 3> <0, 4, 0> <1, 3, 0> <1, 3, 4> ;
<1, 3, 3>       <0, 0, 3> <0, 1, 0> <0, 2, 2> <0, 3, 4> <0, 4, 1> <1, 3, 0> <1, 3, 1> ;
<1, 3, 4>       <0, 0, 4> <0, 1, 1> <0, 2, 3> <0, 3, 0> <0, 4, 2> <1, 3, 1> <1, 3, 2> ;
<1, 4, 0>       <0, 0, 0> <0, 1, 1> <0, 2, 2> <0, 3, 3> <0, 4, 4> <1, 4, 2> <1, 4, 3> ;
<1, 4, 1>       <0, 0, 1> <0, 1, 2> <0, 2, 3> <0, 3, 4> <0, 4, 0> <1, 4, 3> <1, 4, 4> ;
<1, 4, 2>       <0, 0, 2> <0, 1, 3> <0, 2, 4> <0, 3, 0> <0, 4, 1> <1, 4, 0> <1, 4, 4> ;
<1, 4, 3>       <0, 0, 3> <0, 1, 4> <0, 2, 0> <0, 3, 1> <0, 4, 2> <1, 4, 0> <1, 4, 1> ;
<1, 4, 4>       <0, 0, 4> <0, 1, 0> <0, 2, 1> <0, 3, 2> <0, 4, 3> <1, 4, 1> <1, 4, 2> ;

> n := NumberOfVertices(HS) ;
> n ;
50
> 
> assert IsRegular(HS) ;
> d := Maxdeg(HS) ; 
> d ;
7
> assert d eq Mindeg(HS) ;
> assert Diameter(HS) eq 2 ;
> assert Girth(HS) eq 5 ;
> GirthCycle(HS) ;
[ <0, 0, 0>, <0, 0, 1>, <0, 0, 2>, <0, 0, 3>, <0, 0, 4> ]

    Je me suis dit aussi que, peut-être, tu serais super-content de voir la matrice $A \in M_{50}(\Z)$ et l'égalité $A^2 + A = (d-1)I_{50} + J_{50}$ avec $d = 7$. Je me trompe ?

     
    > A := AdjacencyMatrix(HS) ; 
> MnZ := Parent(A) ;
> In := MnZ!1 ;
> Jn := &+Basis(MnZ) ;
> assert A^2 + A eq (d-1)*In + Jn ;
> A ;
[0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0]
[1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1]
[0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1]
[0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0]
[0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0]
[0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0]
[1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1]
[0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1]
[0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0]
  • Chaurien
    Chaurien
    Voici la solution de la RMS
    Bonne journée.
    Fr. Ch.69710
    69712
  • Chaurien
    Chaurien
    Hum... pas très lisible...
  • claude quitté
    claude quitté
    @bisam (et Chaurien)
    Chaurien : avec ce que tu as fourni, même si ce n'est pas très lisible comme tu dis, on doit pouvoir boucher les trous (en cas de besoin) avec le haut de la page 9 de http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS14/pdf

    Je crois comprendre (?) dans cet article, que les auteurs disent, pour le degré $57$, qu'aucun graphe régulier de degré $57$,de diamètre 2, n'a été trouvé. Et pourtant, certains enquêtent sur ce que pourrait être le groupe d'automorphismes d'un tel graphe !

    Il ne faut pas confondre l'unicité des degrés : $3,7,57$ (j'ai omis 1) et l'unicité des graphes. Pour les degrés $3$, $7$, un tel graphe est unique. Et bisam, petit cachotier, le graphe de degré 3 à 10 sommets que tu nous a fait miroiter, c'est le graphe de Petersen, n'est ce pas ? Il y a de jolies constructions de ce dernier graphe, constructions que tu connais probablement.

    Et je manque à tous mes devoirs en ce qui concerne le groupe des automorphismes du graphe de Hoffman & Singleton. Ce groupe est étudié par Hafner (déjà cité) in https://link.springer.com/content/pdf/10.1023/A:1025136524481.pdf, th 4.1 page 12. C'est un groupe d'ordre $252\, 000$.

     
    > time G := AutomorphismGroup(HS) ;
Time: 0.000
> #G ;
252000
> G ;
Permutation group G acting on a set of cardinality 50
Order = 252000 = 2^5 * 3^2 * 5^3 * 7
    (6, 7, 8, 9, 10)(11, 13, 15, 12, 14)(16, 19, 17, 20, 18)(21, 25, 24, 23, 22)(26, 46, 41, 36, 31)(27, 47, 42, 37, 32)(28, 48, 43, 38, 33)(29, 49,
        44, 39, 34)(30, 50, 45, 40, 35)
    (6, 11, 21, 16)(7, 12, 22, 17)(8, 13, 23, 18)(9, 14, 24, 19)(10, 15, 25, 20)(31, 41, 46, 36)(32, 42, 47, 37)(33, 43, 48, 38)(34, 44, 49, 39)(35,
        45, 50, 40)
    (3, 32)(4, 6)(5, 26)(7, 49)(8, 17)(9, 18)(10, 39)(11, 45)(12, 14)(15, 43)(16, 40)(19, 48)(20, 22)(21, 30)(23, 33)(27, 47)(28, 35)(29, 50)(31, 
        36)(34, 38)
    (2, 5)(3, 4)(7, 10)(8, 9)(12, 15)(13, 14)(17, 20)(18, 19)(22, 25)(23, 24)(27, 30)(28, 29)(31, 46)(32, 50)(33, 49)(34, 48)(35, 47)(36, 41)(37, 
        45)(38, 44)(39, 43)(40, 42)
    (1, 2)(3, 5)(7, 10)(8, 9)(11, 15)(12, 14)(16, 19)(17, 18)(21, 23)(24, 25)(26, 32)(27, 31)(28, 35)(29, 34)(30, 33)(36, 47)(37, 46)(38, 50)(39, 
        49)(40, 48)(41, 42)(43, 45)
> IsTransitive(G) ;
true

    On est bien content de savoir tout cela, sans aucun doute.

    bisam : et le groupe des automorphismes du graphe de Petersen, tu vas nous le donner (en même temps que le jolie photo promise) ?
  • P.
    P.
    Hoffman, A.J. 'On a polynomial of a graph' American Mathematical Monthly vol 70 (1963 ) pages 30-36
  • claude quitté
    claude quitté
    @P.
    On n'a pas accès à American Math. Monthly. Enfin, je n'ai pas accès. Tu sais ce que l'article contient ?

    Je n'aime pas pointer wiki mais pour une fois. On voit en https://fr.wikipedia.org/wiki/Graphe_de_Hoffman-Singleton d'abord une jolie photo du graphe de Hoffman & Singleton. Et surtout que ce dernier possède des propriétés mirifiques : il est hamiltonien, le polynôme caractéristique de sa matrice d'adjacence est $(X-2)^{28} (X + 3)^{21} (X- 7)$ ...etc.. Quel veinard, ce bisam.
  • bisam
    bisam
    @Claude : Merci pour tes références, en particulier pour le théorème de Hoffman-Singleton. J'étais encore loin du compte... mais bon, au moins, je n'avais pas révé : on ne trouve pas de solution pour $p=4$ !

    Ensuite, pour la jolie photo, je ne suis pas sûr que vous apprécierez... mais c'est une représentation du graphe que j'ai trouvé pour $p=3$.
    Je n'avais pas du tout reconnu le graphe de Petersen... mais en réordonnant les points correctement, effectivement, c'est bien lui !

    Je ne prends même pas le risque de vérifier si mon algorithme est suffisamment performant pour trouver une solution pour $p=7$ ... et encore moins pour $p=57$ !

    @Chaurien : Merci pour la solution de la RMS. Je n'étais pas allé assez loin dans mes investigations autour des valeurs propres. Je n'avais pas réussi à montrer que le discriminant devait être entier (ni même rationnel).
    Il faut dire que je n'avais pas compris que l'énoncé voulait que l'on montre qu'il n'y avait que 5 valeurs possibles de $p$ (En fait, il y en a 6 si on inclut le graphe ayant 1 seul point et 0 arête).

    Ci-dessous le code Python que j'avais utilisé pour trouver les solutions.
    On voit diverses vagues de recherches... 
    ## ## Importations

import networkx as nx  # pour les graphes
import matplotlib.pyplot as plt  # pour les représentations graphiques
import numpy as np  # pour les matrices
import random as rd  # pour une recherche désespéré, au hasard !

## ## Recherche de solutions


def matrice(positions, n):
    mat = np.zeros((n, n), dtype=int)
    for (l, c) in positions:
        mat[l, c] = 1
    return np.matrix(mat)
    
def aretes(mat):
    n = len(mat)
    l = []
    for i in range(n):
        for j in range(i):
            if mat[i, j]:
                l.extend([(i, j), (j, i)])
    return l

## Recherche récursive quasi exhaustive avec des matrices

@timeit
def solutions(p, stopAtFirst=False):
    if p == 0:
        m = [[0]]
        print(m)
        return m if stopAtFirst else [m]
    
    n = p*p + 1
    I = np.eye(n)
    J = np.ones((n, n)) + (p-1)*I
    sols = []

    def find_position(positions, l, c):
        """Cherche une position de 1 à ajouter à une configuration, au-delà de la
        ligne l et de la colonne c afin qu'elle conserve les propriétés requises"""
        
        if stopAtFirst and (len(sols) > 0):
            return True
        
        if len(positions) == p*n: # on a placé tous les chiffres 1
            m = matrice(positions, n)
            if np.all(m*m + m == J):
                sols.append(m)
                print(m)
                return True
            return False
      
        # on compte le nombre de 1 déjà placés sur la ligne l avant la colonne c
        before_count = sum(1 for (i, j) in positions if i == l and j <= c)
        
        if before_count < p and c+1 < n:
            # on peut en ajouter 1 sur la même ligne
            new = (l, c+1)
        elif before_count == p:
            # on ne peut plus en rajouter
            for k in range(l):
                # on vérifie la compatibilité de cette ligne avec les précédentes
                d = sum(1 for i in range(n) if (k, i) in positions and (l, i) in positions)
                if (k, l) in positions:
                    d += 1
                if d != 1:
                    return False
            # on peut en ajouter 1 sur la ligne suivante
            new = (l+1, max(p-1, l+2))
        else:
            # on est au bout de la ligne et il manque des 1
            return False
        
        # on exécute récursivement avec et sans la nouvelle position
        (l, c) = new
        a = find_position(positions + [new, (c, l)], l, c)
        b = find_position(positions, l, c)
        return a or b

    # on initialise avec une sous-matrice solution du cas précédent
    if stopAtFirst:
        initials = aretes(solutions(p-1, True))
        find_position(initials, 0, p-1)
        return sols[0]
    else:
        for sol in solutions(p-1):
            initials = aretes(sol)
            find_position(initials, 0, p-1)
        return sols

## Affichage des graphes

def graphe_from_adj(mat):
    n = len(mat)
    g = nx.Graph()
    g.add_nodes_from(range(n))
    g.add_edges_from(aretes(mat))
    return g

def montre(mat):
    nx.draw_circular(graphe_from_adj(mat), with_labels=True)
    plt.show()
    
## Recherche itérative gloutonne sur des graphes

@timeit
def solution(p):
    n = p*p + 1
    G = nx.Graph()
    G.add_nodes_from(range(n))
    
    for noeud in range(n):
        #print(noeud)
        voisin = noeud+1
        while len(G[noeud]) < p and voisin < n:
            # voisin peut encore accepter une arête
            if len(G[voisin]) < p:
                # il n'y a pas d'arete entre noeud et voisin
                if voisin not in G[noeud]:
                    # une arete entre noeud et voisin ne crée pas de 3-cycle
                    if all(d not in G[voisin] for d in G[noeud]):
                        # ni de 4-cycle
                        if all(c not in G[d] for c in G[noeud] for d in G[voisin]):
                            G.add_edge(noeud, voisin)
            voisin += 1
        if len(G[noeud]) < p:
            print("plus de place")
    
    mat = nx.adjacency_matrix(G).todense()
    
    plt.close()
    nx.draw_circular(G, with_labels=True)
    plt.show()
    
    return mat

## Recherche récursive complète sur des graphes

@timeit
def solution_rec(p, draw=False):
    n = p*p + 1
    G = nx.Graph()
    G.add_nodes_from(range(n))
    sol = []
    
    def test_edge(G, from_vertex, to_vertex):
        # from_vertex et to_vertex peuvent encore accepter une arête
        if len(G[from_vertex]) < p and len(G[to_vertex]) < p:
            # il n'y a pas d'arete entre from_vertex et to_vertex
            if to_vertex not in G[from_vertex]:
                # une arete entre from_vertex et to_vertex ne crée pas de 3-cycle
                if all(d not in G[to_vertex] for d in G[from_vertex]):
                    # ni de 4-cycle
                    if all(c not in G[d] for c in G[from_vertex] for d in G[to_vertex]):
                        return True
        return False


    def exists_sol(G, from_vertex, to_vertex=None):
        if from_vertex >= n:
            sol.append(nx.adjacency_matrix(G).todense())
            if draw and p==3:
                nx.draw_shell(G, with_labels=True, nlist=[[0,1,4,6,2], [3,9,5,7,8]])
            return True
        
        if len(G[from_vertex]) == p:
            return exists_sol(G, from_vertex+1)
        
        if to_vertex is None:
            to_vertex = from_vertex+1
        
        if to_vertex >= n:
            return False
        
        if test_edge(G, from_vertex, to_vertex):
            G.add_edge(from_vertex, to_vertex)
            if exists_sol(G, from_vertex, to_vertex+1):
                return True
            else:
                G.remove_edge(from_vertex, to_vertex)
        return exists_sol(G, from_vertex, to_vertex+1)
    
    noeud = 0
    voisin = 1
    while noeud < n and any(not G[v] for v in range(n)):
        # on peut remplir avec la première arête qui convient
        # tant qu'il y a un noeud qui n'a pas d'arête
        if test_edge(G, noeud, voisin):
            #print((noeud, voisin))
            G.add_edge(noeud, voisin)
        voisin += 1
        if voisin == n:
            noeud += 1
            voisin = noeud+1
    
    #print("fin de l'itératif")
    if noeud < n:
        exists_sol(G, 0)
    
    return sol
    69718
  • claude quitté
    claude quitté
    @bisam
    Une fois que l'on a un début de pointeur, ce n'est pas difficile de nos jours (le web) de pister la chose. J'en même obtenu des informations en cherchant à ``Graphe de Petersen'', cf http://math.mit.edu/~fox/MAT307-lecture19.pdf : théorème 2, page 3, l'énoncé (et la preuve) du théorème de Hoffman-Singleton. Obtenir les graphes est une autre histoire.

    Pourquoi chercher à ``Petersen Graph'' ? Ben, le tien il est euh ... Comment dire, c'est délicat ... Enfin, disons que j'en ai vu de plus jolis sur le Web. Voici une construction possible, et ensuite je stoppe, promis, juré. On prend comme sommets les $10 = \binom{5}{2}$ parties à 2 éléments de $\{1..5\}$ et on relie $I,J$ par une arête si $I \cap J = \emptyset$.

     
    > V := Subsets({1..5}, 2) ;                                                
> PetersenGraph := Graph < V | { {I,J} : I,J in V | IsEmpty(I meet J) } > ;
> PetersenGraph ;
Graph
Vertex  Neighbours

{ 1, 3 }        { 2, 5 } { 4, 5 } { 2, 4 } ;
{ 1, 5 }        { 2, 4 } { 2, 3 } { 3, 4 } ;
{ 2, 5 }        { 1, 3 } { 1, 4 } { 3, 4 } ;
{ 1, 4 }        { 2, 5 } { 2, 3 } { 3, 5 } ;
{ 4, 5 }        { 1, 3 } { 1, 2 } { 2, 3 } ;
{ 2, 4 }        { 1, 3 } { 1, 5 } { 3, 5 } ;
{ 1, 2 }        { 4, 5 } { 3, 4 } { 3, 5 } ;
{ 2, 3 }        { 1, 5 } { 1, 4 } { 4, 5 } ;
{ 3, 4 }        { 1, 5 } { 2, 5 } { 1, 2 } ;
{ 3, 5 }        { 1, 4 } { 2, 4 } { 1, 2 } ;

> G := AutomorphismGroup(PetersenGraph) ;
> G ;
Permutation group G acting on a set of cardinality 10
Order = 120 = 2^3 * 3 * 5
    (2, 7)(5, 6)(8, 10)
    (2, 8)(4, 9)(5, 6)(7, 10)
    (3, 5)(4, 7)(8, 9)
    (1, 2, 3, 6, 9)(4, 10, 7, 5, 8)

    Son groupe d'automorphismes est un sous-groupe transitif de $S_{10}$ isomorphe à $S_5$.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

Foys +2 Invités