Graphes de Behrend
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Les graphes de Behrend sont des graphes ayant la propriété suivante : toutes leurs arêtes appartiennent à un et un seul triangle. Ils sont basés sur les ensembles d'entiers ne contenant aucune progression arithmétique.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Définition modifier
Soit [m] l'ensemble des entiers de 1 à m. Soit X un sous-ensemble de [m] ne contenant pas trois nombres en progression arithmétique. Autrement dit, pour tout i,j,k distincts dans X, on ne peut avoir j-i = k-j (autrement formulé, on ne peut avoir i+k=2j.)
On définit alors le graphe suivant :
- Il contient 6m sommets.
- Ces sommets sont répartis en trois ensemble de respectivement m,2m et 3m sommets, que nous noterons V1,V2 et V3, et numérotés respectivement de 1 à m, de 1 à 2m et de 1 à 3m.
- Pour tous sommets de x de V1 et y de V2, il y a une arête de x à y si et seulement si y-x est dans X. De même entre les sommets de V2 et ceux de V3. Entre un sommet x de V1 et un sommet z de V3, il y a une arête si et seulement si z-x est dans X.
Le graphe a alors les propriétés suivantes :
- Il contient 3|X|m arêtes
- Il contient |X|m triangles
- Chaque arête appartient à un et un seul triangle.
