Graphes de Behrend

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.

Définition

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.