Quatre (maintenant 3) conjectures qui tuent

christophe c · August 2017

Je ne sais pas si je l'ai déjà fait aussi exhaustivement, mais répéter ne nuit pas ici, je rappelle les 4 grosses conjectures de théorie des graphes. Elles me paraissent totalement hallucinantes (enfin c'est hallucinant qu'elles soient ouvertes et si simples). De plus elles ne nécessitent aucune connaissance et peuvent être racontées à n'importe quel enfant à partir de 11ans. Et elles ressemblent à des "principes logiques" ou presque en un certain sens.

Tous les graphes considérés ici sont non orientés (un arête est une paire de sommets) et sont simples (une seule ou pas d'arête entre deux sommets)

1) Conjecture de Hadwiger: pour tous entiers n et graphe G, si on ne peut pas colorier G avec n couleurs, alors il existe n+1 parties connexes 2 à 2 disjointes et reliées de l'ensemble des sommets de G. 2 parties sont dites reliées quand elles sont disjointes et qu'un des sommets de l'une est relié à un sommet de l'autre.

2) Conjecture de Hedetniemi: pour tous entiers n et graphe fini G, si on ne peut pas colorier G avec n couleurs alors on peut colorier avec n couleurs le graphe dont l'ensemble des sommets est $\{1;..;n\}^G$ et où $f,g$ sont reliées quand pour tout couples $(x,y)$ de sommets reliés de $G$, on a $f(x)\neq g(y)$

Résolue en https://arxiv.org/pdf/1905.02167.pdf
ELLE EST FAUSSE!

3) Conjecture de Vizing: soient deux graphes finis $G,H$. Soit K le graphe obtenu comme sommets les couples $(x,y)$ où $x$ est un sommet de $G$ et $y$ est un sommet de $H$ et où $(x,y)$ est relié à $(u,v)$ quand $(x=y$ et $u$ relié à $v)$ ou $(u=v$ et $x$ relié à $x)$. S'il faut au moins $n$ sommets pour couvrir $G$ et $p$ sommets pour couvrir $H$, alors il en faut au moins $np$ pour couvrir K. Couvrir un graphe veut dire choisir un ensemble $X$ de sommets qui, pour chaque sommet $x$ qui n'est pas dans $X$, il y a un voisin de $x$ qui est dans $X$

4) Evasive Conjecture: soit $n$ un ensemble fini et $A$ un ensemble de parties de $n^2$ stables par passage aux sous-ensembles et par passage à une partie isomorphe. On joue au jeu suivant: Lea joue successivement et dans l'ordre qu'elle veut, mais injectivement les éléments de $n^2$ et Bob lui répond oui ou non. Lea doit s'arrêter avant d'avoir joué le dernier élément de $n^2$ et prendre une position dedans/dehors. Si Bob arrive à lui répondre par un élément $A$ alors qu'elle a répondu dehors ou par un élément hors de A alors qu'elle a répondu dedans, il gagne (son graphe proposé doit être compatible avec les oui non, ie, il doit contenir les arêtes auxquelles il a répondu oui et ne pas contenir celles auxquelles il a répondu non. La conjecture est que Bob a toujours une stratégie gagnante à ce jeu.

Voilà!! En espérant que ça attirera quelques regards d'amateurs et professionnels.

christophe c · August 2017

Je précise que pour les enfants, la conjecture de Hedetniemi a une présentation plus longue mais plus légère sur wikipedia. Le problèmes des "graphistes", c'est qu'ils ont au bas mots 3 ou 4 produits distincts qu'ils appellent "produit cartésien" ou "produit tensoriel" sans motivation très profonde et ça crée des ambiguités pénibles. Le produit en cause dans Hedetniemi est bien "le bon" produit cartésien chez les graphes (j'ai utilisé l'exponentielle qui me parle plus à moi mais peu importe dans la présentation). Mais les graphistes l'appellent "produit tensoriel-cartésien" je crois. Et c'est le produit en cause dans Vizing qu'ils appellent produit cartésien (je ne sais pas trop pourquoi si ce n'est qu'en formant une matrice on "voit bien" la liaison, donc le terme serait motivé par le dessin tout bêtement.

En dualité (mais c'est un peu compliuqué parce que surle fond un graphe n'a pas d'ensemble de sommets, tous les objets de tous les univers sont ses sommets), le dual du produit cartésien (le bon, celui engagé dans Hedetniemi) sera qu'on remplace relié par non relié et et par ou. La dualité étant l'involution offerte par le complémentaire (dans tout l'univers!) de l'ensemble des arêtes.

Bon peu importe. Autre information: si $n$ est un nombre premier (et même une puissance d'un nombre premier), La Evazive Conjecture est prouvée. (Ca peut attirer des gens de signaler ça)

Une conjecture de Hadwiger renforcée (et pas juste inventée par moi), un peu connue est : on dit la même que dans Hadwiger mais on ajoute que les connexes obtenus en contractant des arêtes ne l'ont pas été n'importe comment, mais en contractant toutes et seulement elles, les arêtes formant le "bord" d'une partie du graphe (ie celle qui joignent un sommet dedans à un sommet dehors).

Dernière choise: je suis convaincu que la conjecture de Hadwiger est vraie et qu'en fait elle sera prouvée un jour ou l'autre de la manière suivante: <<presque toute façon de colorier un graphe, du moment qu'on ne déconne pas trop, le colorie avec au plus un nombre de couleurs égal à son nombre d'Hadwiger (ie le cardinal de la plus grosse clique mineure du graphe). Corollaire: un algo pour colorier un graphe avec pas plus de couleurs que son nombre de Hadwiger serait polynomial (et même pas loin de linéaire) selon moi (alors que c'est NP-complet avec le nombre chromatique). C'est pour ça qu'elle est dure à prouver: elle est "tellement évidente" que toutes les tentatives pour la prouver telle quelle sont vouées à l'échec, il n'y a pas de récurrence qui va parler du nombre chromatique, du nombre d'Hadwiger et marcher. Il est "trop vrai" que le nombre chromatique est plus petit que celui de Hadwiger.

christophe c · July 2018

Merci pour le déplacement du fil, j'ajoute des problèmes ouverts qui me semblent assez "philosophiques" et concernent "graphes et déterminants":

https://fr.wikipedia.org/wiki/Conjecture_du_coureur_solitaire

https://fr.wikipedia.org/wiki/Conjecture_jacobienne

https://fr.wikipedia.org/wiki/Matrice_de_Hadamard

https://fr.wikipedia.org/wiki/Étiquetage_gracieux

Il y a aussi (pas trouvé de lien): conjecture de reconstruction: elle dit que si 2 graphes ont leur liste de sous-graphes obtenues en enlevant un sommet isomorphes alors les deux graphes sont isomorphes, sauf exceptions triviales.

babsgueye · July 2018

Salut.
Je me suis intéressé à la conjecture du coureur solitaire, et pense avoir un résultat du cas général.

Je considère les couples $(c_{i}, v_{i}),\;1\leq i\leq k$ l'ensemble des coureurs et vitesses (que je prends entiers) correspondants. Pour un $i_0\in [\![1; k]\!]$, je considère les écarts de vitesses $|v_i - v_{i_{0}}|$ entres le coureur $c_i$ et le coureur particulier $c_{i_{0}}$.

Je trouve qu'en posant:$$t_1 = \dfrac{ppcm\{\dfrac{ppcm\{|v_i - v_{i_{0}}|\}_{1\leq i\leq k,i\neq i_{0}}}{|v_i - v_{i_{0}}|}\}_{1\leq i\leq k,i\neq i_{0}}}{k.ppcm\{|v_i - v_{i_{0}}|\}_{1\leq i\leq k, i\neq i_{0}}}$$, alors pour $$t\in \big[t_{1}; t_{1} + \dfrac{k - 2}{k.max\{v_i \}_{1\leq i\leq k}}\big]$$, la distance entre $c_{i_{0}}$ est chacun des $c_i$ est $\geq \frac1k$.
Et ceci $\forall\; i_o\in [\![1; k]\!]$ ! cqfd.

Cordialement.

Martial · July 2018

@babsgueye : Tu pourrais détailler un peu tes calculs ?
Dans l'état actuel des choses ça me paraît difficile de vérifier la justesse de ton raisonnement, les formules étant particulièrement absconses.

babsgueye · July 2018

La démonstration est en état de prise de notes. Je le posterais après rédaction et...vérifications @Martial.
Mais en fait, par la notation $ppcm\{|v_{i} - v_{i_{0}}|\}_{1\leq i\leq k}$, je veux dire $ppcm (|v_1 - v_{i_{0}}|, |v_2 - v_{i_{0}}|,...,|v_{i_{0}-1} - v_{i_{0}}|, |v_{i_{0}+1} - v_{i_{0}}|,..., |v_{k} - v_{i_{0}}|)$
(où $|x|$ est la valeur absolue de $x$ et $ppcm$: le plus petit commun multiple).

A bientôt.

babsgueye · July 2018

Salut.
Je poste ici ma démonstration comme demandé et attends la critique constructive.

Preuve:
Soient $c_{1}, c_{2},\cdots, c_{k}$ les $k\geq 3$ coureurs et $v_{1}, v_{2},\cdots, v_{k}$, les vitesses respectives des coureurs, distinctes deux à deux et entiers naturels.
Prenons $c_{i_{0}}$, un des coureurs, de vitesse $v_{i_{0}}$.
Considérant qu'à l'instant $t=0$, les différents coureurs commencent à courir partant du point O, à l'instant $t$, l'ensemble $\{|v_{i} - v_{i_{0}}|t\}_{1\leq i\leq k,\;i\neq i_{0}}$ donnent les différentes distances entre les $c_{i},\;i\in [\![1, k]\!]\setminus \{i_{0}\}$ et $c_{i_{0}}$, lorsqu'on considére que les coureurs sont sur une demi-droite d'origine O.
Pour un $i$ donné et que $|v_{i} - v_{i_{0}}|t\in [j + \dfrac{1}{k},\;j + 1 - \dfrac{1}{k}]$, alors la distance sur le cercle entre $c_{i}$ et $c_{i_{0}}$ est $\geq \dfrac{1}{k}$; c'est à dire pour $t\in\big]\dfrac{j + \dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}, \dfrac{j + 1 -\dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}\big[$ et on ne perd pas de généralité en considérant $j$ décrivant $\mathbb{N}$.
Posons $I = [\![1, k]\!]\setminus\{i_{0}\}$
On cherche alors les instants $t\in \bigcap_{i\in I, j\in \mathbb{N}}\big[\dfrac{j + \dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}, \dfrac{j + 1 - \dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}\big]$.
Il suffirait alors pour avoir notre résultat, de montrer que cette intersection contenant $\big[\dfrac{j_{1} + \dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}, \dfrac{j_{1} + 1 - \dfrac{1}{k}}{|v_{i} - v_{i_{0}}|}\big]$ pour un certain $j_{1}$ (dont on va donner le temps $t_{1}$ correspondant), est non vide.
Mais si $t\in\;\big[\dfrac{1}{k|v_{i} - v_{i_{0}}|}, \dfrac{k - 1}{k|v_{i} - v_{i_{0}}|}\big]$, alors la distance entre $c_{i}$ et $c_{i_{0}}$ pour la première fois est $\geq\dfrac{1}{k}$. C'est qu'à l'instant $t = \dfrac{1}{k|v_{i} - v_{i_{0}}|}$, pour la première fois, la distance entre $c_{i}$ et $c_{i_{0}}$ est $\dfrac{1}{k}$.
Par ''extention du ppcm aux fractions'', en prenant $t_{1} = ppcm \big((\dfrac{1}{k|v_{i} - v_{i_{0}}|})_{1\leq i\leq k,\;i\neq i_{0}}\big)$, la distance entre $c_{i_{0}}$ et chacun des $c_{i}$ est $\dfrac{1}{k}$.
Pour le calcul de ce ppcm, rendons les $\dfrac{1}{k|v_{i} - v_{i_{0}}|}$ au mème dénominateur = $ppcm \big((k|v_{i} - v_{i_{0}}|)_{1\leq i\leq k,\;i\neq i_{0}}\big)$.
On a
$\dfrac{1}{k|v_{i} - v_{i_{0}}|} = \dfrac{\dfrac{ppcm \big((k.|v_{i} - v_{i_{0}}|)_{1\leq i\leq k,\;i\neq i_{0}}\big)}{k.|v_{i} - v_{i_{0}}|}}{k.ppcm \big((|v_{i} - v_{i_{0}}|)_{1\leq i\leq k,\;i\neq i_{0}}\big)}$.
Donc à l'instant $t_{1} = \dfrac {ppcm\big((\dfrac{ppcm ((k.|v_{i} - v_{i_{0}}|)_{1\leq i\leq k,\;i\neq i_{0}})}{k.|v_{i} - v_{i_{0}}|})_{1\leq i\leq k,\;i\neq i_{0}}\big)}{k.ppcm \big((|v_{i} - v_{i_{0}}|)_{1\leq i\leq k,\;i\neq i_{0}}\big)}$, la distance entre $c_{i_{0}}$ et chacun des autres $c_{i}$ est de $\dfrac{1}{k}$.
Sachant que la longueur de l'intervalle $]j_{1} + \dfrac{1}{k}, j_{1} + 1 - \dfrac{1}{k}[$, qui est égale à $1 - \dfrac{2}{k}$ est parcourue par le plus rapide des $c_{i}$, soit $c_{i_{m}}$ de vitesse $v_{i_{m}}$ en une durée $d = \dfrac{1 - \dfrac{2}{k}}{v_{i_{m}}} = \dfrac{k - 2}{k.v_{i_{m}}}$, alors pour $t\in\big[t_{1}, t_{1} + \dfrac{k - 2}{k.v_{i_{m}}}\big]$, la distance entre $c_{i_{0}}$ et chacun des $c_{i}$ est $\geq \dfrac{1}{k}$.
De plus:
à l'instant $t_{i} = \dfrac{1}{v_{i}}$, le coureur $c_{i}$ a parcouru la distance $1$. Et donc à l'instant $T_{1} = ppcm \big((\dfrac{1}{v_{i}})_{1\leq i\leq k}\big) = \dfrac{ppcm \big(\dfrac{ppcm( (v_{i})_{1\leq i\leq k})}{v_{i}}\big)}{ppcm( (v_{i})_{1\leq i\leq k})}$ et en ses multiples, tous les $c_{i}$ se retrouvent au mème point O.
Par conséquent, si les coureurs courent assez longtemps, en différents moments $c_{i_{0}}$ sera solitaire.
Et ceci est valable $\forall i_{0}\in\;[\![1, k]\!]$. cqfd.

Cordialement
Merci.

babsgueye · August 2018

Salut.
Deux questions simples liées à Hadwiger !

$a,\; b, \;c, \;d, \;e, \;f, \;g, \;h, \;i$ sont les sommets d'un graphe dont les arêtes sont:

$E = \{ab,\;ad,\;bd,\;bc,\;dc,\;ch,\;de,\;df,\;dg,\;ef,\;fg,\;fi,\;gc,\;gh,\;gi,\;hi\}$ (j'arrive pas à le dessiner ici).

$\bullet$) Ce graphe a-t-il $K_{4}$ comme mineur ?
$\bullet$) Quel est le nombre chromatique de ce graphe ?

PS: si quelqu'un peut me dessiner le graphe dans ce fil, ce serait cool.
Merci. 78730

Champ-Pot-Lion · August 2018

babsgueye, le $t_1$ que tu proposes pour le coureur solitaire est-il différent de $1/k$ ?

babsgueye · August 2018

Je le pense bien en général.

Champ-Pot-Lion · August 2018

Mais peux-tu trouver un contre-exemple ?

babsgueye · August 2018

Prends
$v_1 = 2,\;v_2 = 8,\;v_3 = 6$. pour $k = 3$.

Je trouve $t_1 = \dfrac{1}{6}$.

Champ-Pot-Lion · August 2018

Ah oui, tu as raison. Mais c'est par contre $\left(k \times \gcd(|v_i-v_{i_0}|)_{1\leq i\leq k, i \neq i_0}\right)^{-1}$.

J'ai l'impression que le contre-exemple à $t_1 = 1/k$ est aussi un contre-exemple à ce que tu dis, non ? Au temps $t_1=1/6$, le premier coureur est en position $1/3$ et le deuxième est en position $8/6 = 1 + 1/3$, soit la même position que le premier comme on travaille modulo $1$.

babsgueye · August 2018

Je mets le graphe dont je parle ci-haut en pièce jointe.

[Contenu du pdf ci-joint. AD] 78726

Champ-Pot-Lion · August 2018

Pour ton graphe, $K_4$ est bien un mineur (conserver $d$, $f$, $g$ et $i$ et fusionner le chemin entre $d$ et $i$). Son nombre chromatique est $4$.

babsgueye · August 2018

@AD, si tu peux rectifier: à la place du $g$ en bas, c'est plutôt $i$. Merci.
[Non, je ne peux pas, c'est toi qui possède le source LaTeX de cette image. AD]

@Champ-Pot-Lion, j'ai pas bien compris. Tu conserves quatres sommets, puis tu fusionnes les deux; on nbtient un graphe à trois sommets non ?

En plus $d$ et $i$ ne sont pas voisins !

babsgueye · August 2018

T'as raison @Champ-Pot-Lion. Mais je pense que c'est pas un problème de raisonnement. J'ai plutôt fait une simplification erronée.

A savoir: $ppcm(k.a, k.b) = k.ppcm(a, b)$. C'est faux en général.

Merci.

Champ-Pot-Lion · August 2018

Si si, c'est bien vrai que $\DeclareMathOperator{\ppcm}{ppcm}\ppcm(ka, kb) = k \ppcm(a,b)$. Regardes les valeurs $p$-adiques : le $\ppcm$ correspond à prendre leur $\max$, et on a bien $\max(k+a, k+b) = k+\max(a,b)$.

edit : Pour le graphe, je détaille. On commence par supprimer $a$, $b$ et $e$. Ensuite on fusionne $d$ et $c$ (on appelle $d$ le sommet produit). Puis on fusionne $d$ et $h$, ainsi que $d$ et $i$. On obtient alors le graphe $K_4$, qui est donc un mineur du graphe que tu as donné.

babsgueye · August 2018

J'ai toujours pas compris comment tu fusionnes à la fin $d$ et $i$ et récupérer un graphe à quatre sommets.

Ok t'as raison pour le $ppcm$. Je vais tout revoir.

Champ-Pot-Lion · August 2018

Ah oui, en fait il ne faut pas fusionner $d$ et $i$ à la fin. Il faut seulement fusionner $d$, $c$ et $h$. (Voire même fusionner seulement $d$ et $h$, puis supprimer $a$, $b$, $c$ et $e$.)

christophe c · August 2018

Tes 3 sommets nommés f,g,f (pourquoi le publier avec des sommets différents portant le même nom :-X ?) sont tous les 3 reliés au sommet g du bas. Et pour les rendre tous reliès entre eux, il ne reste qu'à rendre les 2 f reliés: il suffit pour ça de faire de f-d-c un même pays (et comme tu veux, tu peux prendre le f de gauche comme celui de droite).

lesmathspointclaires · August 2018

Le cas de 8 coureurs est encore ouvert : si on suppose sans perte de généralité qu'un coureur a une vitesse nulle et qu'ils démarent tous à $\pi/4$ le problème se pose alors comme suit :

Soit $a_1,a_2,...a_7$ sept réels, pour tout réel $x$, il existe un entier $i\in [1,7]$ tel que $sin(a_ix)$ et $cos(a_ix)$ sont positifs

babsgueye · August 2018

Bonjour.
@cc c'est une erreur frappe de nommer des sommets différents du même nom. Je le change dans cette pièce jointe. Mais je vois toujours pas le $K_4$.

[Contenu du pdf (corrigé) joint. AD] 78754

christophe c · August 2018

Les 4 pays suivants:

pays f+d+c
pays g
pays h
pays i

Il se touchent tous 2 à 2

babsgueye · August 2018

Ah cette notion de mineur ! Ok j'ai vu @cc. Merci.

babsgueye · August 2018

Je reviens pour la même question.
Le nombre chromatique de ce graphe (pièce jointe) est $5$, mais je n'arrive pas encore à voir un mineur $K_5$.
Quelqu'un pour me le sortir ?
Merci.

[Contenu du pdf joint. AD] 78786

Champ-Pot-Lion · August 2018

Tu vois que $\{a,b,c,d,j\}$ forme presque un sous-graphe complet ? Il suffit de relier $a$ et $c$ grâce à une fusion.

lesmathspointclaires · August 2018

Est-ce que la conjecture du coureur solitaire (les coureurs commencent en même temps) implique la même conjecture quel que soit la configuration de départ ?

babsgueye · August 2018

Je vois pas encore comment tu as fait @Champ-Pot-Lion. Peux-tu préciser ?
Merci.

Champ-Pot-Lion · August 2018

On fusionne $a$ et $h$, puis on supprime $e$, $f$, $g$ et $i$.

babsgueye · August 2018

@Champ-Pot-Lion est qu'on a la même définition de la notion de mineur ? Comment tu peux fusionner $a$ et $h$ sans toucher $b,\;c,\; ou\;d$ qu'on doit conserver ?
Merci.

Champ-Pot-Lion · August 2018

Ah oui, tu as raison ! Je suis allé trop vite. Mais ça m'étonnerait que le nombre chromatique du graphe que tu donnes est $5$, puisqu'il est planaire. La conjecture (prouvée pour $K_5$ je crois) n'implique donc pas que $K_5$ est mineur.

babsgueye · August 2018

J'ai appliqué l'algorithme de Welsh Powell pour trouver le nombre chromatique, ça m'a donné $5$. S'il y a pas de mineur $K_5$, on détiendrait un contre-exemple de la conjecture.

Coucou à @cc !

Champ-Pot-Lion · August 2018

L'algorithme de Welsh Powell ne donne qu'un majorant du nombre chromatique. C'est un heuristique. Ton graphe est planaire, il est donc forcément 4-colorable, ou alors tu auras aussi trouvé un (très petit) contre-exemple à ce théorème prouvé par ordinateur.

babsgueye · August 2018

En fait je suis juste entrain d'essayer de comprendre la conjecture et la notion de mineur. Je pensais Welsh Powell optimal.
Je vais encore chercher.

Merci.

christophe c · August 2018

@bab: la conjecture de Hadwiger dit que tu peux colorier n'importe quel graphe en utilisant un nombre de couleur inférieur ou égal au nombre de sommets de la plus grande clique mineur de lui.

babsgueye · August 2018

Merci @cc, mais t'as pas vraiment répondu à ma question.
Y a pas le feu, je vais chercher au hasard comme il n'y a pas d'algorithme efficace pour donner le nombre chromatique.

babsgueye · August 2018

Ok j'ai trouvé. Le nombre chromatique est en fait $4$.

Merci.

Sylvain · August 2018

Pour Hadwiger il y a sûrement une notion de dualité sous jacente. Il faudrait trouver une façon naturelle d'associer à un graphe G un graphe dual G* tel que G**=G et tel que le nombre chromatique de G* soit canoniquement égal au nombre de sommets de la plus grande clique mineur de G. Ensuite il faudrait prouver que le nombre chromatique est préservé par dualité.

Sylvain · August 2018

Ou pourrait aussi imaginer associer à un graphe G un espace vectoriel V_G (sans V_G, t'as rien :-D) tel qu'à deux sommets A et B reliés par une arête correspond un couple de vecteurs de V_G dont le produit scalaire est non nul et à deux sommets C et D non reliés correspond un couple de vecteurs de V_G orthogonaux.

Sylvain · August 2018

Et du coup un endomorphisme unitaire de V_G correspondrait à un automorphisme de G.

Kramer · August 2018

Y'a plus qu'à.:-D

Sylvain · August 2018

Peut-être d'ailleurs qu'on peut exiger V_(G*)=(V_G)*. J'arrête là pour ce soir.

Sylvain · August 2018

En fait je pense qu'on peut attribuer une connectivité $ \kappa(a,b) $ à toute paire de sommets $ (a,b) $ d'un graphe $ G $ valant $ 1 $ si une arête les relie et $ 0 $ sinon. On pourrait alors associer à un sommet $ a $ un vecteur $ u_{a} $ tel que $\langle u_{a}, u_{b}\rangle=1-\kappa(a,b) $ (pas incohérent a priori car on suppose qu'aucune arête ne va d'un sommet vers lui-même). Le graphe complet à $ d $ sommets correspond alors à un espace vectoriel de dimension $ d $ ayant une base orthonormée et il faudrait alors voir cette dimension comme le nombre chromatique du graphe $ G^{*} $ dont l'espace vectoriel associé est le dual de celui associé à $ G $.

Qu'en pense l'ami Christophe ?

Sylvain · August 2018

Dans ce cadre passer d'un graphe à un mineur de celui-ci revient à réduire (au sens large) la connectivité entre deux sommets : si $ H $ est un mineur de $ G $, on a $ \kappa_{H}(a,b)\le\kappa_{G}(a,b) $ pour tout couple $ (a,b) $ de sommets.

Sylvain · August 2018

Extraire un mineur d'un graphe correspond donc à orthonormaliser l'espace vectoriel associé.

Sylvain · August 2018

En outre le principe de la coloration de graphe est que deux sommets reliés par une arête sont de couleurs différentes. On peut donc définir l'homochromie $\eta_{G}(a,b) $ de deux sommets $ a $ et $ b $ de $ G $ comme valant 1 si leur couleur est identique et 0 sinon. Ainsi $ \eta_{G'}(a,b)=1-\kappa_{G'}(a,b) $ où $ G' $ est le "dernier mineur" (mineur d'un mineur d'un mineur...) isomorphe à un graphe complet qu'on puisse extraire de $ G $. On obtient in fine autant de classes d'homochromie donc de couleurs donc le nombre chromatique de $ G $ que le nombre de vecteurs orthonormaux deux à deux de l'espace vectoriel associé au "dernier mineur" de $ G $, donc le nombre d'Hadwiger de $ G $.

Sylvain · August 2018

L'idée clé est que la connectivité diminue au cours de l'extraction d'un mineur et donc lorsqu'elle est minimale le nombre de classes d'homochromie est maximal donc vaut le nombre chromatique. Par construction ce nombre est égal au nombre de Hadwiger du graphe initial.

Sylvain · August 2018

Je reprends mon idée de graphe dual. A un graphe G on associe son graphe dual G* formé des mêmes sommets et tel que pour toute paire (a,b) de sommets distincts on a $ \kappa_{G^{*}}(a,b)=1-\kappa_{G} (a,b)$. Ainsi un mineur $ H $ de $ G $ a pour dual un graphe $ H^{*} $ ayant au moins autant d'arêtes que $ H $ au bout d'un certain nombres d'itérations. Quand ce nombre d'arêtes est maximal on a obtenu un graphe complet dual d'un ensemble de $\chi_{G}$ sommets isolés.

Sylvain · August 2018

Comme deux sommets de G de même couleur ne peuvent être reliés, ils le sont dans G*. L'ensemble des sommets d'une même couleur forment donc un sous-graphe complet de G*. Il y a donc exactement $ \chi_{G} $ sous-graphes complets (éventuellement réduits à un sommet) $ K_{k_{1}} $ , $ K_{k_{2}} $,..., $ K_{k_{\chi_{G}}} $ avec $ \sum_{i=1}^{\chi_{G}}k_{i}=s_{G} $ le nombre de sommets de $ G $ . On peut contracter dans chaque $ K_{k_{i}} $ les arêtes et fusionner les sommets en un seul pour obtenir un graphe $ G' $ à $\chi_{G} $ sommets. En prenant son dual on obtient un graphe connexe G'* mineur de G isomorphe au graphe complet à $ \chi_{G} $ sommets : en effet s'il n'était pas complet il y aurait deux sommets de couleurs différentes non reliés. Mais alors ces sommets disons Vert et Rouge seraient reliés dans G' donc dans G*. Il n'y aurait donc aucune arête dans G connectant un sommet vert et un sommet rouge : une seule couleur (rouge ou vert) au lieu de deux suffirait alors pour avoir une coloration de G. Donc le nombre chromatique serait inférieur d'une unité à ce qu'il est ce qui est impossible.