Théorie des graphes extrémaux

Discipline

branche de la théorie des graphes

domaine: combinatoire extrémale · théorie des graphes

Pour comprendre

La théorie des graphes extrémaux est une branche de la théorie des graphes. Elle se rattache aussi à la combinatoire extrémale.

Ce qu'elle étudie

Son domaine est situé à l'intérieur de la théorie des graphes et de la combinatoire extrémale. Elle en constitue une branche particulière.

Où elle se place

Elle appartient à la théorie des graphes et à la combinatoire extrémale.

flowchart TD
  P0[théorie des graphes] --> D([Théorie des graphes extrémaux])
  P1[combinatoire extrémale] --> D([Théorie des graphes extrémaux])

Cas d’usage

Cherchons combien de liens un graphe peut contenir sans faire apparaître un motif interdit. Les points sont ses sommets, les liens ses arêtes. Un graphe atteignant le maximum est dit extrémal.

Interdisons $K_4$, quatre sommets tous reliés entre eux par six arêtes. Sur $6$ sommets, $15$ arêtes sont possibles : les $2^{15}=32\,768$ graphes examinés donnent au plus $12$ arêtes sans $K_4$.

Construisons trois groupes de deux sommets. Relions chaque sommet à tous ceux des autres groupes, jamais à ceux du sien :

$$2\times2+2\times2+2\times2=12$$

Parmi quatre sommets pris dans trois groupes, deux sont forcément dans le même groupe et ne sont pas reliés : aucun $K_4$.

Sur $5$ sommets, les $10$ arêtes possibles donnent $1\,024$ graphes. Le maximum est $8$, avec des groupes de tailles $2,2,1$ :

$$2\times2+2\times1+2\times1=8$$

Sur $9$ sommets, trois groupes de trois donnent $3\times3+3\times3+3\times3=27$ arêtes sur $36$, soit les trois quarts. Ajouter une arête dans un groupe crée un $K_4$ avec un sommet de chacun des autres groupes. Le théorème garantit le maximum $27$ et cette unique forme de graphe, à renommage des sommets près.

Interdisons maintenant un cycle de longueur $4$ : un parcours en carré revenant au départ. Deux sommets ne doivent jamais avoir deux voisins communs. Un carré de quatre arêtes est interdit ; un triangle avec une arête pendante, attachée à un seul sommet, est permis : quatre arêtes aussi.

Les maxima calculés sont :

$4$ sommets : $4$ arêtes.
$5$ sommets : $6$ arêtes.
$6$ sommets : $7$ arêtes sur $15$, moins de la moitié.

Sur cinq sommets, dessinons un « nœud papillon », deux triangles partageant un sommet. Numérotons ses sommets de $0$ à $4$ : les arêtes relient $0$ à $1$, $0$ à $2$, $1$ à $2$, $0$ à $3$, $0$ à $4$, $3$ à $4$. Ajouter l'arête de $1$ à $3$ crée le cycle $1,2,0,3,1$ : aucune arête de plus sans carré.

Sur six sommets, interdire un triangle permet $9$ arêtes ; interdire $K_4$, $12$ ; interdire un carré, seulement $7$. Le maximum dépend du motif interdit, et le carré est le plus contraignant des trois.

Sources

Wikidata CC0-1.0

wikidata Q739245