Considérons la projection ci dessous (ce n'est pas forcément la projection d'un figure avec des traits droits, ça peut être un sac de noeuds)
Les paires de triangles possibles,et si elles sont imbriquées sont :
ABC DEF NI
ABD CEF NI
ABE CDF I enlacement 2 (donc définitivement pas la représentation d'une figure à traits droit
ABF CDE NI
ACD BEF NI
ACE BDF I enlacement 1
ACF BDE NI
ADE BCF I enlacement 1
ADF BCE I enlacement 1
AEF BCD NI
On voit que la somme des enlacements vaut 5, ce qui est bien impair.
Choisissons un croisement :
CE et BD
CE passe au dessus de BD. Croisons les, maintenant CE passe en dessous de BD.
Désormais, ABD CEF est imbriquée (enlacement 1) et ACE BDF n'est plus imbriquée.
Les imbrications de toutes les autres paires ne sont pas affectées.
Un enlacement a augmenté de 1, et l'autre a diminué de 1. La somme des enlacements fait toujours 5, la parité n'a donc toujours pas changée.
Comme la parité sera toujours impaire, on n'aura toujours au moins une paire avec un enlacement non nul (donc imbriquée)
On peut faire le test en effectuant d'autres croisements, ce sera toujours vrai.
Bonjour,
weierstrass : Soit, on ne peut qu'agréer à ce genre de dénombrement sur le schéma présenté avec des fils souples par-dessus/par-dessous.
Mais rien ne prouve que c'est un ensemble valide dans l'espace avec des segments de droites entre des points pré-donnés. Une fois cette validation faite, alors on peut se permettre....
Cela me fait penser à un passage préalable dans une usine de traitements chimiques avant de pouvoir comparer à la démonstration sur chacun des 3 polyèdres (à 2, 1 ou 0 points intérieurs).
Mais bel effort
Si la propriété est vraie dans le cas de fils souples, elle est vraie à plus forte raison dans le cas de segments droits.
Et je n'ai pas fait beaucoup d'effort, je n'ai fait que traduire la démonstration de mathématiciens bien plus brillant que moi. Robertson et Seymour, bien qu'il ne soient pas à l'origine de cette démonstration mais l'ait juste reprise, ont apporté de nombreuses contributions aux rapports entre les graphes et la topologie, notamment via l'étude des familles de graphes fermées par mineurs. (comme cette famille ci), et ont démontré le théorème de Robertson-Seymour, qui est l'un des plus grands théorèmes de théorie des graphes (et l'un de mes préférés - le préféré?)
Bonjour,
Je n'ai pas dû comprendre la démonstration,
Comment peut-elle être générale si on doit d'abord, sur le graphe plantaire représentatif, déterminer quel segment est dessus pour chaque croisement de deux segments.
Et bien quand on projette notre graphe, comme on connait ou sont placés les points, on peut également savoir quel trait sera au dessus ou au dessous lors de la projection. Et ça, on peut le représenter sur notre graphe planaire. A partir de cette projection, la démonstration nous dit que la somme des enlacements est impaire. On en conclut donc qu'il n'y a pas d'enlacement...
Quelle que soit la manière de dessiner un graphe planaire complet, en choisissant quand on veut passer au dessus ou en dessous, la propriété restera vraie. Mais on ne peut pas déterminer le nombre d'enlacement juste avec le dessin que tu as joint. En effet, un infinité d'ensembles de points donneront exactement le même dessin, et ces ensembles de points n'auront pas forcément le même nombre de triangles imbriqués.
Bonjour,
weierstrass : Si je reprends bien l'énoncé : "Montrer qu'il est toujours possible...."
Vous dites qu'en préalable : "quand on projette notre graphe, comme on connait ou sont placés les points, on peut également savoir quel trait sera au dessus ou au dessous lors de la projection..."
Je comprends bien, mais le problème n(est pas de montrer sur un ensemble de 6 points,
il faut montrer qu'il n'y a pas d'ensemble de 6 points qui n'aie pas de triangles imbriqués.
Il vous faudrait donc déterminer tous les cas des traits dessus ou dessous dans toutes les projections possibles ?
Je suis peut-être trop insistant...
Le dessin que j'ai donné est effectivement juste un exemple, car vous m'aviez demandé un exemple pour clarifier ma démo.
---> weierstrass : Une dernière fois , ensuite j'abandonne.
Je ne comprends justement pas la logique dans la d&monstration que vous citez :
Rebonjour à tous les deux .
J'avoue que j'ai beaucoup de mal à comprendre la démonstration car aucune hypothèse n'est clairement explicitée . On part d'un graphe à six points dans un espace de dimension trois que l'on projette ( proprement ) sur un plan en laissant apparaître à chaque intersection les chemins supérieurs et inférieurs . Pour chaque paire de triangles ( il y en a dix ) on définit l'enlacement comme la somme des enlacements aux poins d'intersections des lacets des deux triangles . Jusque là c'est très clair mais un peu moins après .
Qu'appelle-t-on enlacement total de la projection ? Est-ce la somme des enlacements aux différents points d'intersections ou la somme pour les paires de triangles( on parle bien sûr modulo 2 ) ? Qu'est-ce qui assure que les deux sommes sont les mêmes ? Pourquoi sont-elles toujours impaires ?
Après si les réponses sont celles attendues , la solution coule de source .
Encore faut-il combler les blancs
Imod
Bonsoir,
En revoyant le premier lien donné par weierstrass, tout est démontré depuis 1993. La réponse était simple : c'est démontré par et pour toutes les façons de projeter toute configuration de 6 points.
A défaut il faut détailler, ce qui me semble bien plus complexe que de raisonner directement sur polyèdres ayant 2, 1 ou 0 points dans leur enveloppe convexe en espace 3D
@vham
Il n'est peut-être pas indispensable de rappeler à chaque message la beauté et la simplicité de votre démonstration avec l'enveloppe convexe . On va admettre que cette idée est géniale et essayer de simplifier l'idée de Weierstrass qui n'est peut-être pas aussi compliquée qu'elle en a l'air .
Imod
Imod
Bonjour,
Ce qui tient en 5 lignes c'est la justification du résultat : "The graph K6, (the complete graph on six vertices) has no linkless embed-ding."
la preuve se fait "By studying the effect of a crossing change in a regular projection, it is easy to see that......By checking an arbitrary embedding we can establish that this invariant equals 1."
Pour moi aucune difficulté à comprendre ce résultat de l'étude des "LINKLESS EMBEDDINGS OF GRAPHS IN 3-SPACE"
Ce qui me pose problème, c'est comment, d'une projection arbitraire (K6) comportant les dessus-dessous des arcs qui se croisent sur cette projection plane (définition de l'embedding si je ne me trompe), on arrive à la configuration exacte (dans l'espace) donnée par les 6 points imposés quelconques (4 non coplanaires).
En effet, si je bouge un point pour ajuster un croisement de la projection , ce peut être un autre croisement qui se trouve modifié d'abord. et même si on met des arcs de courbe sans bouger les points, rien ne prouve que des segments de droites restitués conviendront.
L'énoncé parle bien de triangles, pas de courbes fermées dans l'espace.
Vham
K6 n'est pas une projection arbitraire, c'est le graphe complet à 6 sommets. Dans notre problème ici, on a 6 points reliés de toutes les façons possibles, donc on a K6.
Ce qu'on veut montrer que pour n'importe quel plongement (embedding) du graph K6 dans l'espace à 3 dimensions, alors ce plongement ne contient pas deux cycles intriquées (linkless embedding).
Ce qui est démontré, c'est bien : il n'y a pas de plongement de K6 sans paire de cycles imbriquées (The graph K6, (the complete graph on six vertices) has no linkless embed-ding), tout les plongements possibles sont donc traités dans cette démonstration, y compris les plongements où les arcs sont droits.
A la fin de la démo, il est dit qu'en consultant un plongement arbitraire, on va trouver que la somme des enlacements est impaire (By checking an arbitrary embedding we can establish that this invariant equals 1). Cette phrase n'est pas la conclusion de la démonstration mais une étape de la démonstration.
En combinant les propositions "Si l'on passe d'un plongement à un autre en croisant deux arcs, la somme des enlacements des deux plongements à la même parité " et "il existe un plongement telle que la somme des enlacements est impaire", on déduit "tout plongement à une somme d'enlacements impaire"
Dans la dernière phrase de la démo, la démonstration ne précise pas quel plongement elle prend, puisque ça marcherait avec n'importe lequel et ce n'est pas le point le plus difficile de la démo.
Imod
Désolé, je n'avais pas vu ton dernier message.
Encore une fois, la démo n'est pas mon idée, elle est exposée dans le papier dont j'ai donné le lien. (Et la démo est encore plus vieille puisqu'elle provient d'un autre article de d'autres auteurs (mais d'accès payant).
La démo donnée est vraiment simple et concise, je dois croire que ma traduction la rend beaucoup plus alambiquée que ce qu'elle n'est...
Et pitié, dis moi que tu as compris la démo
Bonjour,
Le graphe que je vous avait proposé le 11-07-20 à 12:22 n'est-il pas un K6 ? C'est la projection sur un plan d'une configuration complète (15 segments entre 6 points) de l'espace.
J'ai bien dit que la démonstration sur le graphe K6 ne me posait aucun problème, c'est lorsque le graphe est plongé dans l'espace 3D que je me pose des questions sur comment on l'adapte aux 6 points pré-donnés.
Si cela ne vous interpelle pas, vous n'êtes pas obligé de justifier....
Comme le même graphe, avant que l'on y porte quel brin est dessus ou dessous, peut être la projection de diffêrentes configuration dans l'espace, je vois mal comment on peut éviter de s'intéresser à quel polyèdre on a affaire.
Salut à tout les deux
J'ai fait un petit break pendant quelques jours , il n'y a rien de mieux pour remettre les idées en place
Il y a plein de choses qui m'interpellent dans la démonstration de Weierstrass , essentiellement par manque de connaissances mais j'aimerais bien asseoir quelques certitudes .
Une première question :
On projette les six points sur un plan et on note pour chaque "intersection" le segment qui passe au dessus . On choisit deux triangles dont les sommets sont ces six points et dont deux côtés se "croisent" . On conserve ces deux côtés et on échange les deux autres sommets . A priori cet échange change le nombre de points d'intersections ( 2 , 4 , 6 ) et possiblement la parité souhaitée ? Non ?
Imod
Imod
On ne compte pas le nombre d'intersections, on compte les enlacements. Les intersections permettent de déduire les enlacement, mais le nombre d'intersections n'a pas réellement d'incidence sur l'enlacement. Deux cordes avec un enlacement de 1 peuvent, après avoir été projetées, avoir 2, 4, 6, 8... intersections. Il suffit que l'une des cordes passent plusieurs fois au dessus de l'autre pour produire des intersections qui n'augmentent pas l'enlacement. Regarde le lien sur les enlacements que j'avais donné dans ma démo, ça explique pas mal de trucs.
On n'échange jamais de sommets, on croise juste les traits. Si à un endroit, une corde passait au dessus de l'autre, on la fait passer en dessous. Ca ne modifie pas le nombre d'intersections, ça modifie juste le type d'une seule intersection. En modifiant une intersection, on modifie l'enlacement des deux paires de triangles avec cette intersection. Comme on modifie de + ou - 1 l'enlacement de 2 paires de triangles, la parité ne change pas.
Quand je parlais d'intervertir deux sommets, c'était pour montrer qu'il y a exactement deux paires de triangles correspondant à une intersection.
Toutes les configurations peuvent être obtenues à partir d'une configuration arbitraire en ne faisant croiser que 2 traits à la fois.
Bonjour,
Les "explications" sur l'enlacement et la somme de ces enlacements ne sont pas toujours três limpides sur internet. Les pré-requis pour manipuler ces croisements et jauger correctement cet "embedding" sont aussi .....il y faut une approche précise des éléments de la théorie.
Oui, la page anglaise est bien plus claire sur le sujet :
La notion de plongement en revanche n'est pas compliquée :
Un graphe est un ensemble de relations entre des sommets, et le plongement d'un graphe est un dessin de ce graphe. Un graphe reste le même qu'il soit dessiné avec des croisements ou non, avec des arcs courbes ou non, du moment que les sommets sont reliés de la même manière. Par contre, les plongements de graphes dépendent de la façon dont on dessine.
Bonsoir,
C'est une autre Géométrie. Dès qu'on regarde la définition on est dans :
" This is formalized as "regular homotopy", which further requires ....."
On n'est plus dans la répartition simple de points séparés (ou non) dans l'espace par un plan.
Entièrement d'accord avec Vham , s'il y a une idée facile avec les entrelacements , elle doit pouvoir s'écrire en termes simples dans le cas où aucun chemin ne "vrille" autour d'un autre . Ici j'ai l'impression que l'on noie le poisson dans une théorie fumeuse dont je n'ai pas les clés . En bref Weierstrass a sans doute raison mais pour l'instant je ne vois pas pourquoi .
Imod
PS : J'interpelle régulièrement et souvent maladroitement untel ou untel , ce n'est jamais agressif , une simple envie de comprendre
Bonsoir,
Imod : la théorie des entrelacs et graphes (sic en français) n'est quand même pas une "théorie fumeuse". Elle a des implications intéressantes en biologie entre autres et un large champ d'applications ....
Il est vrai (weierstrass : Merci) que le problème des courbes enlacées en espace 3D (ici les triangles) ressort plus de cette théorie que de la géométrie des polyèdres. On formalise bien pour ceux-ci, et on n'a effectivement pas immédiatement les clés de cette autre approche.
Vham La théorie des entrelacs et des nœuds est effectivement utile ici pour éviter les arguments géométriques sur les polyèdres.
La démonstration donnée n'est pas dans une autre géométrie. Les homotopies s'appliquent à différents types de géométrie, et celui dans R3 en particulier, donc il n'y a pas de problème.
Imod
Dans le cas ou aucun chemin ne vrille autour de l'autre, l'enlacement est de 0 puisque les deux courbes sont séparées. Si une courbe passe au dessus de l'autre et en ressort en repassant par dessus, on est toujours avec un enlacement de 0, car on peut séparer les boucles. (la première est juste posée au dessus de la deuxième.
Si on fait passer la première au dessus et qu'on la fait ressortir au dessous, les deux courbes vont être liées et d'enlacement 1.
Si on fait passer au dessus, en dessous, en dessus, au dessous, les deux courbes vont être liées, mais on a fait deux tours dans l'enlacement sera de deux.
Si on fait passer au dessus, en dessous, en dessous, au dessus, les deux courbes ne seront pas liées. En effet, on passe deux fois consécutivement en dessous, donc on peut tirer cette partie pour enlever ces deux intersections. On se retrouve alors avec deux passages au dessus, on peut donc séparer les deux courbes. Donc l'enlacement sera de 0. On a fait un tour dans un sens et un dans l'autre, les deux tours ce sont donc annulés en terme d'enlacement. Pour la définition précise de l'enlacement, voir sur wikipedia le mode de calcul de l'enlacement via l'étude des intersections (on définit des orientations aux deux courbes, on classifie les intersections comme positive ou négative selon le l'orientation au croisement, puis on somme sur les intersections avec le bon signe.
On peut voir mon schéma pour des exemples de calculs d'enlacements. (NI est non enlacé, donc avec enlacement 0. I est enlacé, et je précise l'enlacement)
Notons que, contrairement à ce que je pensais, on peut avoir deux courbes avec un enlacement de 0 et qui sont liées (nœud de Whitehead). Ca ne change pas la démo, puisque on prouve qu'il existe au moins une paire avec un enlacement impair, et tout les courbes avec enlacement impair sont liées.
J'ai vraiment l'impression d'être le boulet dans cette affaire
Je pense avoir compris ce qu'est l'enlacement surtout pour cette configuration plutôt simple où on tourne pas autour du pot . J'ai aussi compris que les croisements de fil laissent invariants la parité des enlacements . En fait depuis le début ce n'est pas vraiment ça qui m'enquiquine : pourquoi la somme des enlacements serait-elle toujours impaire ? Sur ton exemple c'est le cas mais tu as choisi la configuration la plus simple avec une enveloppe convexe à six points . Il me semble qu'il y a pas mal de variantes et dans les autres cas on retombe assez vite dans la complexité de la solution de Vham .
En bref , pourquoi la somme des enlacements est-elle toujours impaire ?
Imod
Il me semble pourtant que au début du sujet, on était tombé d'accord sur le fait que l'on puisse passer d'une configuration arbitraire à n'importe quelle autre, même enveloppe convexe ou non, en déplaçant continuement les points, et en ne croisant jamais plus de deux traits à la fois. Il suffit donc qu'une configuration soit impaire pour que toutes les autres aient la même parité.
Je vais continuer à faire le boulet . Chaque fois que tu as parlé de déplacements , tu faisais allusion aux lignes mais jamais aux sommets .
Pourquoi un sommet traversant une ligne ( pourquoi deux ? ) va-t-il conserver la parité sur l'ensemble des enlacements ?
Désolé d'être aussi lourd mais vraiment je ne comprends pas
Imod
D'accord, je vois ce qui te bloques.
Il faut effectivement montrer que l'enlacement est un invariant de la configuration 3D, et que donc l'enlacement est le même quelle que soit la projection 2D.
Cet invariant est une propriété fondamentale des noeuds, ce qui explique pourquoi ce n'est pas redémontré dans le papier, mais ça mérite quand même d'être observé ici. Finalement, ce n'est pas plus compliqué qu'un croisement de trait. Quand un sommet passe un trait, les deux intersections de l'autre côté restent du même type (relativement à l'orientation des courbes). Du coup, l'enlacement ne change pas.
Si on raisonne en 3D, un sommet qui croise un trait ne correspond à aucun croisement dans l'espace, c'est donc normal que l'enlacement ne change pas.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :