Matroïde

[invitec1dae955]

Bonjour, j'ai un petit problème qui me fatigue depuis quelques jours.

La notion de matroïde utilisée ici est celle de Whitney, à savoir:

un matroïde est un couple où est un ensemble fini non vide et vérifie les deux propriétés suivantes:

1. , implique . (hérédité)

2. , , , tel que . (propriété de l'échange)

Il s'agit de montrer la chose suivante:

Si est un matroïde, alors avec est aussi un matroïde.

Pour le faire, j'ai utilisé la définition donnée du matroïde.
La propriété d'hérédité est très facile à prouver mais j'ai du mal avec celle de l'échange car jusqu'ici, je n'ai réussi à prouver qu'elle était vérifiée que sous certaines conditions et pas dans le cas général. Si quelqu'un a une idée ou une piste, je l'en remercie d'avance.
-----

[invite2bd4953c]

Salut,

avec cette définition des matroïdes, cet exercice n'est en effet pas vraiment trivial. Par contre, il y en a une, dite de "caractérisation par les bases" qui lui supprime toute difficulté (mais cette caractérisation n'est à nouveau pas si évidente que ça à démontrer), bref.

Des notions de bases et deux questions préparatoires sur les matroïdes, qui simplifient un peu le discours:

- Les éléments de I sont appelés les "indépendants" de M (par analogie avec l'algèbre linéaire).
- Une base de M est un indépendant de M qui est maximal pour l'inclusion.
Exo 1: Vérifie (si tu ne l'as pas déjà fait) que toutes les bases de M ont le même nombre d'éléments (ce qui d'ailleurs, dans le cas linéaire, permet de définir la dimension d'un espace vectoriel)
Exo 2: être un indépendant de M est équivalent à être contenu dans une base de M.

Ainsi, I' n'est rien d'autre que les parties F de E pour lesquelles il existe une base de M disjointe de F.

Pour démontrer que satisfait l'axiome d'échange, il suffit donc, comme tu l'as dit, de montrer que si avec |F|<|G|, alors il existe un avec .

C'est à dire qu'il faut trouver un de sorte qu'il existe une base de M disjointe de .

Voici de quoi démarrer (il est conseillé de faire un dessin):

Par définition de G, il existe une base B de M disjointe de G (cette base peut éventuellement rencontrer F). Considère , dont tu constateras immédiatement que c'est un élément de I.

De même, il existe une base de M contenue dans , et tu pourras démontrer facilement que ceci implique que est contenu dans une base B' de M disjointe de F (voir exo 2)!

Il nous suffit ainsi pour conclure de montrer qu'il existe tel que F+x reste disjointe de B'!

A partir d'ici, je te laisse terminer en utilisant l'exo 1. N'hésites pas à poser d'autres questions si tu le souhaites.

Bon courage.

OBerge

[invitec1dae955]

Avant toute chose, merci beaucoup de prendre le temps de me répondre.

J'ai bien compris le raisonnement, mais j'ai une question: (en reprenant les mêmes notations)

Comment peut-on être sûr que ne contient pas ? Parce que si c'est le cas, j'ai l'impression qu'on ne peut pas conclure...

Puisqu'on ne trouvera pas de tel que est disjoint de .

Merci encore.

[invite2bd4953c]

On démontre par l'absurde que n'est pas contenu dans B'.

Une indication supplémentaire pour cela: si tu supposes que l'inclusion est satisfaite, alors tu peux montrer facilement (en utilisant les résultats intermédiaires) que , ce qui contredit le résultat de l'exercice 1.

[A voir en vidéo sur Futura]

[invitec1dae955]

Ok, donc si j'arrive à montrer que ladite inclusion n'est pas satisfaite, alors je peux conclure; je vais voir ça...

Merci!!

[invitec1dae955]

Ca y est, j'ai enfin trouvé. La démonstration par l'absurde reposait entre autres sur l'utilisation du fait que . Merci, le problème me semble résolu.