Hadwiger, contre-exemple ? — Les-mathematiques.net The most powerful custom community solution in the world

Hadwiger, contre-exemple ?

Salut.
J'ai jeté un coup d'œil à la conjecture de Hadwiger. J'ai construit ici un graphe d'ordre $8$ dans lequel je ne vois pas de $K_6$, mais je n'arrive aussi pas à le colorer avec $5$ couleurs. Qui a le temps d'y jeter un coup d'œil pour me dépanner est bienvenu.

Je n'arrive pas à mettre le graphe sur cette page du forum. Est-ce possible ?

[Babs, joindre une copie d'écran. ;-) AD]116272
«1

Réponses

  • $K_6$ est bien un mineur de ton graphe.

    Pour obtenir $K_6$ tu dois contracter l'arête $fb$ puis l'arête $ch$.


    Edit : arrête->arête
  • Ah ok, je me rends compte que j'ai cherché un sous-graphe à la place d'un mineur.$K_6$.

    PS : mais pourquoi ça a été déplacé dans shtam ? C'est juste une question simple sur les graphes.
  • Effectivement ce fil n'aurait pas dû être déplacé dans shtam... bon c'est ton ancienne réputation qui t'a précédée babsgueye.
  • Trop difficile de réfléchir avec les mineurs. Peut être une récurrence sur l'ordre du graphe en partant d'un $K_k$.
    Merci raoul.S
  • @raoul.S j'ai mieux regardé ta proposition, mais les sommets fb et ch ne sont toujours pas adjacents.
  • J'ai dit qu'il faut contracter les arêtes $fb$ et $ch$. En contractant ces arêtes, les sommets $f$ et $b$ fusionnent ainsi que les sommets $c$ et $h$.

    Si tu lis l'article de Wikipedia sur les mineurs ICI tu verras comment il faut procéder pour contracter une arête.


    Edit : arrête->arête
  • Ok c'est l'arrête $fh$ qui vient les lier. Je pense qu'on pouvait aussi contracter les arrêtes $be$ et $ce$. C'est un sujet trop difficile. Même une bonne réponse serait difficile à rédiger.
  • Encore une intervention sur un sujet que tu ne maîtrises pas.
  • Bonjour

    Heureusement que les mathématiciens font des interventions sur des sujets qu'ils ne maîtrisent pas. Sinon, on en serait toujours à l'âge de pierre avec des vieux ronchons psychorigides qui prétendent que tout ce qu'il ne connaissent pas est impossible.

    Vive l'exploration mathématique !
  • Bon en tout cas, arrêtez de faire une faute d'orthographe à "arête".
  • Même si on n'est pas si vieux et si ronchon, on peut trouver [ici, l'adjectif de son choix] cette prétention à réfuter ou démontrer une conjecture difficile tous les quinze jours sans apprendre la moindre technique évoluée – et, dans le cas du jour, même la définition de mineur, sans laquelle la conjecture ne peut même pas être énoncée, n'est pas comprise.
  • PLM,

    les gens qui font systématiquement des raisonnements faux ne font pas progresser les mathématiques ;-)

    On pourrait croire que tu es nouveau sur le forum, que tu n'as jamais lu les interventions fausses de Babsgueye.

    Cordialement.
  • Je m'y frotte sans aucune prétention.
    L'essentiel est de ma faire ma propre idée de la difficulté du problème en y réfléchissant et en apprenant en mème temps à mes temps libres. C'est quand mème pas interdit d'autant plus que j'ai démontré la conjecture du coureur solitaire sur cette lancée.
    Dans le cas du jour, c'est pas que je ne comprends pas la notion de mineur, c'est que là il faut juste bien regarder. Le lien de raoul.S je l'avais lu depuis longtemps.
  • Tu n'as pas démontré la conjecture du coureur solitaire. Tu as écrit un texte tellement confus que personne n'a envie de chercher les erreurs.
  • babsgueye a écrit:
    d'autant plus que j'ai démontré la conjecture du coureur solitaire sur cette lancée

    Cette affirmation c'était pour donner une bonne raison d'avoir déplacé ce fil dans shtam je suppose...
  • Babsgueye,

    arrête de mentir. Tu as rédigé un texte sur la conjecture du coureur solitaire qui comportait de nombreuses erreurs et n'était en rien une démonstration. Une démonstration qui ne convainc que toi est une illusion.
  • Comment être capable de démontrer quelque chose qu’on ne sait même pas formuler ?

    Pourquoi cet aveuglement ?
  • @Dom tu ne m'a toujours pas encore sorti ton contre-exemple pour $k = 4$, concernant la conjecture du coureur solitaire. Pour énoncer la conjecture, il me suffit d'aller piocher dans Wikipedia. Quand mème ! Soit plus convaincant.
  • (:P)
    (:P)

    Merci à toi pour cette magnifique blague.
  • babsgueye a écrit:
    je ne comprends pas la notion de mineur

    C'est une forme d'essentialisation. Pour comprendre, prenons le graphe des interactions en entreprises. Chaque nœud est une personne. Chaque arête est un lien social.
    • A-t-on vraiment besoin de 2 stagiaires : un pour copier, un pour coller ? Non. Donc on va embaucher un seul nouveau stagiaire qui va copier-coller. Il aura toutes les interactions des deux personnes précédentes. On a fusionné deux nœuds.
    • A-t-on vraiment besoin d'un employé pour éventer le patron ? Non. On peut donc supprimer un nœud isolé.
    • Le beau Bobby de la livraison a-t-il vraiment besoin de toujours draguer Josiane, la secrétaire ? Non. On peut donc supprimer une arête.
    Ainsi, pour décrire l'entreprise, on peut faire un graphe beaucoup plus simple que le graphe intégral (j'évite le mot "complet") : c'est le mineur.
    Ce qui est essentiel pour décrire l'entreprise est évidemment subjectif. Josiane aurait réduit le graphe à son arête avec Bobby.
  • Babsgueye est une femme ?

  • Voilà ce que babsgueye appelle « convaincre ».
    C’en est désolant d’une part et peut-être même triste d’autre part, sauf s’il est épanoui.

    Remarquez qu’il dit lui-même « la démo n’est pas pour le moment correcte ».
    Pardon, mais ça ne s’appelle donc pas une démonstration.
  • Mais il est toujours vrai que tu ne trouves pas un contre-exemple. Et je pense que tu ne peux pas en trouver.
    Tant qu'un comité de lecture n'aura pas approuvé la démonstration, je ne ferais que penser qu'elle est correcte, ça ne veut pas dire que j'ai pas confiance en moi, sur ce que j'ai écrit. C'est juste que je détiens pas de droit de véto sur les maths.
    Quelle que soit l'assurance qu'on peut avoir sur une preuve de maths, on attend toujours d'être apprécié, qu'on soit amateur ou professionnel.

  • Elle est belle celle-là aussi.

    Écoutez-moi :
    Je travaille dans $\mathbb R$.
    Théorème : $1=2$.
    Preuve : bla ble bli blo blu donc $1=2$.

    J’ajoute :
    J’ai envoyé ça à tous les journaux qui existent sur Terre.
    Et surtout : « Tant qu'un comité de lecture n'aura pas approuvé la démonstration, je ne ferais que penser qu'elle est correcte »
    Puis-je espérer un retour de cette presse sérieuse ?
    Si je n’en ai pas, c’est que ce que je dis est correct ?
  • @Dom un grand farceur ?
  • Non, je ne suis pas ton miroir ;-)

    Bon WE.
  • Merci. A toi de mème.
  • 21012311312926198.png
    Cette image, c'est la même que la tienne.
    Tu vas me dire que c'est un détail, un de plus, mais il me semble que la 1ère des choses à faire, quand tu analyses un graphe, c'est de le présenter de façon à ce que les symétries et/ou les conclusions soient visibles.C'est aussi un signe de politesse envers les personnes qui vont t'aider.
    Raoul t'a proposé certaines contractions, on voit immédiatement par symétrie qu'il y a d'autres contractions possibles.
    Babsgueye a écrit:
    Tant qu'un comité de lecture n'aura pas approuvé la démonstration, je ne ferais que penser qu'elle est correcte,
    Tu voulais certainement dire le contraire : Tant qu'un comité de lecture n'aura pas rejeté la démonstration, je ne ferais que penser qu'elle est correcte.

    Aujourd'hui, tu penses que ta conjecture est correcte. Et quand un comité de lecture aura approuvé ta démonstration, tu changeras d'avis, et tu diras que finalement, elle est fausse ?
    Mais il est toujours vrai que tu ne trouves pas un contre-exemple. Et je pense que tu ne peux pas en trouver.
    Quand on fait des maths, on essaie d'écrire des phrases qui ne sont pas ambigues.
    Ce que tu veux dire, c'est ça : [small]Mais il est toujours vrai que tu ne trouves pas un contre-exemple à la conjecture. Et je pense que tu ne peux pas en trouver.[/small] ?
    C'est ça, ou c'est autre chose que tu voulais dire ?
  • Le problème avec Babsgueye, c'est que l'expérience de l'échec ne lui est pas profitable. En général, quand on croit avoir trouvé un truc intéressant, mais que ce truc s'avère faux, normalement on devient méfiant, c'est là la clé de l'expérience acquise. Cela vaut pas seulement pour les maths, mais pour toute activité, en particulier pour tout métier. Le cas Babsgueye est à part : l'échec ne lui profite pas, sitôt la faille trouvée, il se tourne vers un autre sujet, qu'il n'a pas plus étudié que les précédents, et sort une nouvelle proposition qui fatalement est tout aussi fausse. Si Babsgueye exerce un métier, il devrait pourtant comprendre cela naturellement. Parce qu'il est impossible d'avoir un tel comportement dans un milieu professionnel.

    Mais Babsgueye est plus fort encore: malgré tous les échecs sur tous les sujets qu'il a présentés, si un seul d'entre eux n'a pas été formellement démonté, parce que la communauté finit pas se lasser de ses logorrhées, alors il reste persuadé que c'est lui qui a raison pour ce seul sujet.

    Comme pour le barde Assurancetourix, les avis sont partagés: lui se trouve génial, tous les autres le trouvent exécrable. Mais quand il ne dit rien, c'est un gai compagnon.
  • Si tu ne connais pas la notion de mineur pense à celle d'espace abstrait, comme le plan etc. Informellement Hadwiger dit que tout graphe dessinable dans l'espace machin peut être colorié avec pas plus de couleurs que le nombre de sommets de la plus grosse clique dessinable dans ledit espace machin.

    De mon téléphone.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • lourrran a écrit:
    Tant qu'un comité de lecture n'aura pas rejeté la démonstration, je ne ferais que penser qu'elle est correcte.

    Non @lourrran je voulais dire statué
    lourrran a écrit:
    Mais il est toujours vrai que tu ne trouves pas un contre-exemple à la conjecture
    Je veux dire un contre-exemple à ce que j'ai dit.

    @nodgim, ce que je fais c'est proposer à moi mème et au forum des problèmes que d'éminents mathématiciens nous ont demandés de regarder. Que je trouve ou que je ne trouve n'est pas le problème, j'ai déjà expliqué que ce qui m'importe au premier plan est de me faire moi-même une idée de la difficulté du problème au lieu de de passer mon temps à le contempler. Ce qui n'est pas sérieux c'est de ne rien essayer de savoir sur le sujet, quand on est dans la disposition d'accepter les corrections des autres.

    Merci @cc.
  • Je pose la mème question sur ce graphe d'ordre $7$. Je n'y vois pas de $K_6$ et je ne peux pas le colorer avec $5$ couleurs.

    PS : je n'arrive toujours pas à le mettre sur la page du forum
    [Une fois affiché sur ton écran, tu prends un outil de capture d'écran qui va te donner un fichier jpeg ou png que tu pourras joindre à ton message. AD]116346
  • Pour trouver un contre-exemple à ce que tu as dit, il faudrait d'abord donner une signification à ce que tu as dit. Qui s'en charge, toi ?
  • J'ai pas compris. De quoi tu parles @lourrran ?
    Sinon est-ce que tu peux m'expliquer clairement comment mettre le graphe qui est en fichier joint sur la page du forum.

    Merci @AD, mais j'ai pas encore pigé.
  • Pour poser le graphe, si j’ai compris : il suffit d’en faire une capture.
    En gros, c’est une photo et non un pdf ou autre document.
    Un *.jpg par exemple.
  • @babsgueye tu es sûr que tu veux t'attaquer à cette conjecture ?

    On peut trouver une coloration avec 5 couleurs :

    a: 5
    b: 4
    c: 1
    d: 5
    e: 2
    f: 4
    g: 3
  • 1 . Tu te connectes sur un site d'hébergement d'images. Moi j'ai pris pour ce dessin CASIMAGES
    2. Tu fais un 'Drag-&-Drop de ton explorateur Windows vers ce site, puis tu cliques sur le bouton 'Envoyer les images'.
    3. Le site te donne différentes URLs pour récupérer l'image. Il faut choisir la dernière URL (lien Source, Grande Image)

    4. Tu copies ce lien dans ton message, avec le bouton 'image'.

    Pour ton nouveau graphe, voici une image plus adaptée :

    210124050332241171.png

    On voit clairement que les 5 points A,C,E,F,G sont saturés entre eux, chacun est relié aux 4 autres. Donc on leur attribue 5 couleurs différentes.
    Ensuite, D a forcément la même couleur que A , puis B a la même couleur que F.
    Et ce coloriage convient.
    Mais évidemment, il faut faire l'effort d'abord de dessiner le graphe comme il faut pour que ce coloriage devienne évident.


    Ce que je disais par ailleurs, c'est que tu demandes un contre-exemple à ta 'pseudo-démonstration' du coureur solitaire.
    Mais comme ta pseudo-démonstration est un texte qui n'a aucun sens, il faut d'abord réécrire ce texte, avant de chercher un contre-exemple.
  • @raoul.S pour le moment, je suis juste en train de chercher une bonne intuition.
    Mais c'est vrai que je commence à me dire que c'est un peu trop difficile. Peut-être que j'arrive pas encore à saisir ce qui doit me faire croire que c'est vraie. Avec les mineurs tout est un peu caché.
    Mais bon...
  • @lourrran pour le cas du coureur solitaire, je peux dire que j'ai un peu fait un exposé donc le but été de faire comprendre d'où venait mon intuition. Mais la démonstration proprement dite ne considère que trois cas de figure qui peuvent mème se ramener à deux d'une manière générale.
    1) Le cas où on trouve $p\leq k$ premier avec tous les $a_i$.
    2) Le cas où les $a_i$ sont consécutifs.
    3) sinon

    Pour les cas 1) et 3) j'ai proposé une méthode pour trouver $\alpha_0$ tel que $t_{i_{0}} = \dfrac{\alpha_0}{p}$ est un instant où $c_{i_{0}}$ est solitaire.
    Pour le cas 2) , il suffit de prendre $t_{i_{0}} = \dfrac1k$.

    Mais si tu veux toujours en discuter, tu dois poster dans le dit fil.
  • Bonne idée.
    Essaye de rédiger ton bazar pour $k=4$ du coureur solitaire pour comprendre que ce que tu écris n’est pas clair.
    Si ça marche, je serai le premier à te le dire.
    Mais tu n’oseras pas le faire. Pourtant c’est simple à adapter ton texte à $k=4$ si tu y crois.
    Je te dirai ce qui ne va pas.
  • @Dom c'est la deuxième fois que tu me poses la mème question et je t'avais répondu là-dessus. Ceux qui ont démontré pour des cas particuliers n'ont certainement pas adopté la mème démarche que moi. IL n'est pas question d'adapter la démonstration pour le cas particulier $k = 4$. Le cas $k = 4$ est déjà pris en compte dans la démo. Ce qu'on peut demander c'est de l'appliquer pour n'importe quel cas $k = 4$. Et là je suis prêt à le faire si tu n'y arrives pas.

    Ps : il serait plus propice de poser la question sur le fil en question
  • :-S
    En fait tu ne comprends même pas ce que je te dis. 8-)
    Tu sembles aveuglé.
    Une dernière fois :
    Si tu as une preuve qui marche pour n’importe quel $k$ alors TOI, TU DOIS ÊTRE CAPABLE de la récrire pour $k=4$.
    Ce n’est pas à moi de le faire, non, désolé.
    Ça aurait le mérite de valider au moins ta preuve pour ce cas particulier ou bien de trouver quelque chose à corriger.
  • Sur la conjecture de Hadwiger (qui est un des énoncés auquel j'ai le plus réfléchi dans ma vie), j'ai acquis la conviction qu'elle est un cas ULTRAPARTICULIER d'une "évidence" pas trop longue en nombre de caractères, mais pas très courte non plus. On n'est pas du tout sur un énoncé habituel de maths, sur des nombres entiers ou des structures hyper particularisées où le côté ouvert vient plus de la lourdeur des hypothèses très fortes faites pour choisir les bonnes.

    Hadwiger reste malgré tout beaucoup plus général et profond que ces problèmes ouverts sophistiqués aux hypothèses fortes, vu la grande généralité phénoménale qu'il affirme.

    A l'instar de Hedetniemi, bien que j'y crois beaucoup moins que pour Hedetniemi, il se pourrait qu'elle soit fausse ce qui expliquerait qu'on n'ait même pas dégagé de preuve non valable, mais intuitive comme pour Brouwer (dont l'intuition dépasse de très loin en concision les preuves officielles trouvées)

    Cela dit, j'aurais tout de même tendance à penser qu'elle est vraie et prouvable, mais je ne suis pas assez objectif vu mon engagement en sa faveur. Le pire c'est que j'avais trouvé des arguments, et comme un con je les ai oubliés à remettre au lendemain leur rédaction.

    Je ne le ferai pas dans ce fil, mais j'ai une preuve que si elle est fausse ce serait encore plus un scoop que si les zéros de Riemann se mettaient à déconner totalement, et grandement à partir d'une certaine hauteur :-D

    En résumé sa fausseté aurait beaucoup de conséquences sacrément exotiques, ça je peux le prouver. Mais entre l'exotisme et 0=1 il y a un monde.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Salut Christophe, pardonne-moi si je dis une ineptie titanesque, mais penses-tu qu'il puisse y avoir un lien entre Hadwiger et (une généralisation de) l'homologie ?
  • Salut Sylvain, je ne connais pas assez l'homologie (même pas du tout à vrai dire, ayant reporté une initiation qu'on m'a proposé sur le ofrum d'ailleurs, faudra que j'y revienne).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Salut.
    J'ai le mème problème avec ce graphe dans lequel je ne vois pas un $K_7$ et que je ne peux colorer avec 6 couleurs.
    Merci.116620
  • Bien sûr, ce qui suit ne va pas te dissuader de continuer mais bon. Ton graphe est bien coloriable en six couleurs et contient un $K_7$ et même un $K_8$.
    In:
    dG = {'a':['b','c','f','e','l','m'], 'b':['m','d','g','e','f','c'], 'c':['m','d','j','e','f'],'d':['e','f','i','h','k','g'],'e':['g','h','i','f'],'f':['g','h','i'],'g':['i','h','l','k'],'h':['i','l','j','k'],'i':['j','k','l'],'j':['m','l','k'],'k':['l','m'],'l':['m']}
    G = Graph(dG)
    G.show()
    
    G.chromatic_number()
    G.coloring()
    
    Out:
    6
    [['f', 'l'], ['h', 'm'], ['c', 'g'], ['b', 'i'], ['e', 'k'], ['a', 'd', 'j']]
    
    In:
    K8 = Graph({k:range(k) for k in range(1,8)})
    G.minor(K8)
    
    Out:
    {0: ['e'],
     1: ['f'],
     2: ['c', 'b', 'j'],
     3: ['a', 'm', 'l'],
     4: ['d', 'k'],
     5: ['g'],
     6: ['h'],
     7: ['i']}
    
    116624
  • babsgueye va revenir avec des graphes de plus en plus complexes, jusqu'à ce qu'il soit irréalisable de vérifier par ordinateur que la conjecture fonctionne, et en conclura qu'il a trouvé un contre-exemple. C'est une toute nouvelle méthode de démonstration (déjà appliquée avec brio à a conjecture du coureur solitaire) qui nous fait pleinement entrer dans le futur des mathématiques ! B-)-
  • Apparemment, Math Coss dispose d'un outil magique qui répond instantanément aux questions que se pose Babsgueye en théorie des graphes.

    Je ne suis pas spécialiste, mais je crois deviner que cet outil s'appelle Sage. Du coup, cherchons un peu.
    Et là, en 3 minutes, je trouve ce lien : Sage en ligne

    Waow, je vais donc copier le code proposé par Math Coss, et hop, j'ai la décomposition en 6 couleurs, ... immédiatement. Magique.

    La version de base, celle en ligne, qui ne sait à peu près rien faire, elle sait répondre aux questions posées par Babsgueye !

    On m'a toujours dit qu'un bon ouvrier a de bons outils.
    Quand on s'attaque à des choses compliquées, et qu'on refuse d'apprendre à utiliser les outils adaptés, ça donne quoi : on se ridiculise.
  • C'est super @Math Coss. J'ai eu tout le mal.
    Non @Poirot. Je veux juste comprendre ce qui se passe. Et je vais démissionner parce que si j'arrive pas à convaincre avec des valeurs numériques ; des calculs numériques (conjecture du coureur solitaire), à plus forte raison avec celle-là qui demandera d'expliquer ce qui se passe.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!