Graphe de Frankl-Rödl

Le graphe de Frankl-Rödl ${\mathrm{FR}}_{1/3}^3$ est formé des sommets d'un cube tridimensionnel et des arêtes entre des sommets à distance deux.

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

Modèle:Multiple image Soit n être un entier positif, et soit $\gamma$ un nombre réel dans l'intervalle de l'unité $0\le \gamma \le 1$. On suppose de plus que $(1-\gamma )n$ est un entier pair. Le graphe de Frankl-Rödl noté ${\mathrm{FR}}_{\gamma }^n$ est le graphe qui a pour sommets les $2^n$ sommets de l'hypercube $[0,1{]}^n$ de dimension $n$, 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 $(1-\gamma )n$. La condition que $(1-\gamma )n$ 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 ${\mathrm{FR}}_{1/3}^3$ 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 ${\mathrm{FR}}_{1/2}^4$relie les sommets à distance deux d'un hypercube à quatre dimensions et est formé de deux copies du graphe de Turán Modèle:Math. Les deux graphes deFrankl-Rödl de dimension cinq, à savoir ${\mathrm{FR}}_{1/5}^5$ et ${\mathrm{FR}}_{3/5}^5$, 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 ${\mathrm{FR}}_{\gamma }^n$ est un graphe régulier, de degré

$(\genfrac{}{}{0ex}{}{n}{(1-\gamma )n}).$

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

Comme l'on montré Modèle:Harvsp, lorsque $\gamma \le 1/4$, la taille d'un ensemble indépendant maximal dans un graphe de Frankl-Rödl est

$n(2-\mathrm{\Omega }(\gamma {)}^2{)}^n.$

Dans cette formule Modèle:Formule dans cette formule est une Ω a le sens usuel. Pour les valeurs constantes de Modèle:Mvar et variables de Modèle:Mvar, cette taille de l'ensemble indépendant maximal est une petite fraction des $2^n$ 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 deuxModèle:,.

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 $\gamma =1/4$. 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-colorablesModèle:,Modèle:,. 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.

Articles liés

• Graphe de Turán
• Graphe de Clebsch
• Conjecture des jeux uniques