Graphe de Frankl-Rödl

En théorie des graphes  et en théorie de complexité des calculs, un graphe de  Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe  les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents.

Les graphes de  Frankl-Rödl portent le nom de Péter Frankl et Vojtěch Rödl, qui ont démontré en 1987 que, pour certaines valeurs des paramètres du graphe, ils ont un nombre de stabilité (taille du stable maximal) petit et un nombre chromatique élevé. Depuis, ces graphes sont devenus intéressants en complexité de calcul, comme des exemples qui sont difficiles pour la programmation semi-définie basée sur des algorithmes d'approximation du problème de  couverture par sommets et pour les problèmes de coloration de graphes. Ses propriétés algorithmiques ont été utilisés pour remettre en question la conjecture des jeux uniques.

Définition et exemples 

Soit n être un entier positif, et soit  un nombre réel dans l'intervalle de l'unité . On suppose de plus que  est un entier pair. Le graphe de Frankl-Rödl noté  est le graphe qui a pour sommets les   sommets de l'hypercube   de dimension  , et dans lequel deux sommets sont adjacents lorsque leur distance de Hamming (le nombre de coordonnées dans lesquelles les deux diffèrent) est exactement . La condition que   est un entier pair empêche le graphe d'être biparti. Le graphe de Frankl-Rödl est nécessairement non connexe, avec au moins une composante connexe pour chacun des deux côtés de la bipartition du graphe hypercube correspondant.

Comme premier exemple, le graphe de Frankl-Rödl  relie les sommets à distance deux dans un cube tridimensionnel ordinaire, comme le montre l'illustration. Géométriquement, ce motif de connexion produit une forme connue sous le nom d'octangle étoilé; du point de vue de la théorie des graphes, il est formé de deux composantes connexes, dont chacune est un graphe complet à quatre sommets. De même, le graphe Frankl-Rödl relie les sommets à distance deux d'un hypercube à quatre dimensions et est formé de deux copies du graphe de Turán . Les deux graphes deFrankl-Rödl de  dimension cinq, à savoir  et , sont formés chacun de deux copies complémentaires de graphes de Clebsch, de degré cinq et dix respectivement.

Propriétés 
Le graphe de  Frankl-Rödl  est un graphe régulier, de degré

 

Il hérite les symétries de son hypercube sous-jacent, ce qui en fait un graphe symétrique.

Comme l'on montré , lorsque , la taille d'un ensemble indépendant maximal dans un graphe de Frankl-Rödl est

 

Dans cette formule  dans cette formule est une  Ω a le sens usuel.
Pour les valeurs constantes de  et variables de , cette taille de l'ensemble indépendant maximal est une petite fraction des  sommets du graphe. Plus précisément, cette fraction est inversement proportionnelle à une fonction exponentielle de n et une fonction polynomiale enla taille du graphique. Parce que chaque couleur dans la bonne coloration du graphe de Frankl-Rödl forme un ensemble indépendant avec peu de sommets, le nombre de couleurs doit être grand (une fonction polynomiale de la taille du graphique).

Complexité algorithmique 

Le problème de couverture par sommets est de trouver un ensemble de sommets qui est adjacent à toute arête du graphe. Ce problème et NP-difficile mais peut être approché dans un taux d'approximation de valeur 2, par exemple, en prenant les extrémités des arêtes d'un couplage maximal. La preuve que c'est le meilleur taux d'approximation possible d'un algorithme d'approximation en temps polynomial est fournie par le fait que, lorsqu'il est représenté comme un programme semi-défini, le problème a un écart d'intégralité de deux ; cet écart est le rapport entre la valeur de solution de la solution entière (une couverture par sommets valide) et sa relaxation semi-définie. Selon la conjecture des jeux uniques, pour de nombreux autres problèmes le rapport d'approximation optimal est fourni par l'écart d'intégralité de leur relaxation semi-définie. Cependant, les graphes de FranklRödl sont les seuls cas connus de couverture par sommets pour lesquels l'écart d'intégralité peut être aussi mauvais que deux.

Des graphes de Frankl–Rödl ont également été utilisés pour étudier des approches semi-définies pour la coloration de graphes. Dans cette optique, on étudie la 3-coloration de graphe en relation avec les graphes Frankl-Rödl de paramètre . Les graphes de Frankl-Rödl avec cette valeur du paramètre ont un nombre chromatique élevé ;  la programmation semi-définie est néanmoins incapable de les distinguer des graphes 3-colorables. Cependant, pour ces graphes, les méthodes algébriques basées sur des sommes polynomiales de carrés peuvent fournir des bornes plus fortes qui montrent qu'il faut beaucoup de couleurs. Ce résultat est un défi à l'optimisation de la programmation semi-définie et à la correction de la conjecture des jeux uniques.

Notes et références

Articles liés 
 Graphe de Turán
 Graphe de Clebsch
 Conjecture des jeux uniques

Frankl-Rödl