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.

Cet article ne cite pas suffisamment ses sources (janvier 2023).

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 ?

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.

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 :

1. Il contient 6m sommets.
2. Ces sommets sont répartis en trois ensemble de respectivement m,2m et 3m sommets, que nous noterons V₁,V₂ et V₃, et numérotés respectivement de 1 à m, de 1 à 2m et de 1 à 3m.
3. Pour tous sommets de x de V₁ et y de V₂, 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 V₂ et ceux de V₃. Entre un sommet x de V₁ et un sommet z de V₃, il y a une arête si et seulement si z-x est dans X.

Le graphe a alors les propriétés suivantes :

1. Il contient 3|X|m arêtes
2. Il contient |X|m triangles
3. Chaque arête appartient à un et un seul triangle.

• Portail des mathématiques