Quatre (maintenant 3) conjectures qui tuent
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.
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.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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.
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.
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.
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.
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.
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.
$v_1 = 2,\;v_2 = 8,\;v_3 = 6$. pour $k = 3$.
Je trouve $t_1 = \dfrac{1}{6}$.
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$.
[Contenu du pdf ci-joint. AD]
[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 !
A savoir: $ppcm(k.a, k.b) = k.ppcm(a, b)$. C'est faux en général.
Merci.
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é.
Ok t'as raison pour le $ppcm$. Je vais tout revoir.
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
@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]
pays g
pays h
pays i
Il se touchent tous 2 à 2
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]
Merci.
Merci.
Coucou à @cc !
Je vais encore chercher.
Merci.
Y a pas le feu, je vais chercher au hasard comme il n'y a pas d'algorithme efficace pour donner le nombre chromatique.
Merci.
Qu'en pense l'ami Christophe ?
admettons l'impossible, il faut trouver la faute dans le raisonnement exposé ci-avant, ou quoi ?