Inscription / Connexion Nouveau Sujet
Bonjour Foxdevil,
Je n'ai lu que le théorème de Hall qu'en diagonale, j'avoue que je cherche toujours une solution immédiate au problème posé.
Le comptage du nombre de systèmes communs de représentants dans le cas fini permet peut-être d'en fournir une autre (si cela aboutit).
En prenant quelques cas simples, on se rend compte assez rapidement que pour classes de
éléments, il n'y a pas un nombre unique de systèmes communs, mais que tout va dépendre des partitions P et P'.
Il y a un maximum : systèmes communs (quand P=P'), et il y a certainement un minimum : avec mes transpositions, pour aller de P à P', on échange les éléments 2 à 2 ; au début, chaque échange élimine des systèmes communs de représentants, qui peuvent être recréés au fur et à mesure des échanges. Le nombre de systèmes possibles va dépendre du plus ou moins grand "mélange" des éléments des classes de P' par rapport à celles de P.
Exemple : P = { {a,b}, {c,d}, {e,f} }, P' = { {a,c}, {b,d}, {e,f} }. En échangeant b et c, on détruit les systèmes communs (a,c,e), (a,c,f), (b,d,e) et (b,d,f). On passe de 2^3 (systèmes communs pour P=P'), à 2^3-4=4 systèmes communs. Avec P' plus mélangé par rapport à P, le nombre de systèmes va diminuer, mais à force de mélanges, on peut reconstituer les classes.
Prenons pas exemple
Du coup prenons plutôt
Je n'ai lu que le théorème de Hall qu'en diagonale, j'avoue que je cherche toujours une solution immédiate au problème posé.
Foxdevil,
J'ai regardé rapidement la solution avec la théorie des graphes. Peux-tu me mettre sur la voie : un sommet = une classe ou un élément d'une classe ?
coa347,
Un sommet est bien une classe de la partition, oui.
Un graphe c'est très visuel, c'est des points lles sommets) avec des traits qui les relient (les arretes).
Tu fais bien de regarder un peu les graphes, d'autant plus que je viens de trouver une formule sur le nombre de couple parfait. Ce qui permettrait de déduire le nombre de systèmes de représentants.
Mais je mettrai tout ça plus tard...
Dans ce cas, que représente les arêtes ? En fait je ne comprends pas comment on peut tirer une propriété sur des éléments à partir d'un graphe dont les sommets sont des classes. Mais je n'ai sûrement pas assez approfondi.
En fait je construits un graphe spécial lié au problème où on a des arrêtes entre deux sommets du graphe si et seulement si leur intersection est non vide et si l'un est dans P et l'autre dans P'.
C'est ce qui en fait un graphe biparti. D'une part jai les sommet de P et d'autres part ceux de P'. Et les seules arrêtes que j'ai passent de P à P'.
En fait avoir un couplage parfait dans le graphe signifie que j'ai réussi à appairer les classes de P et de P' deux à deux mais avec intersection non vide (puisque ce sont les seuls arrêtes du graphe).
N'importe qui dans chacune de ses intersections respectives peut représenter faire partie d'un système de représentants.
(En fait je viens de réaliser qu'on a pas tellement besoin de la bijection mentionnée avant. Le couplage parfait nous donne directement un système de représentants 
)
Bonjour Foxdevil,
Quand il n'y a que deux classes, le dénombrement du nombre minimum de systèmes communs de représentants s'obtient assez facilement: pour n pair,
pour n impair (pour un ensemble à n éléments).
Quand il y a plusieurs classes et que (nombre de classes = nombre d'éléments par classe) aussi : c'est
.
Sauf erreur.
Avec un effort supplémentaire, on doit pouvoir trouver ce nombre minimum pour n et m quelconques. D'où la démonstration cherchée.
Bon, je vais regarder la solution avec la théorie des graphes.
Super, ça marche dans le cas fini !
Pour toute partie X de P, les éléments de X sont reliés à au moins autant d'éléments de P' qu'en comporte X (cela parait assez évident, mais cela se voit pour des raisons de même cardinalité entre les classes).
Donc ce graphe biparti admet un couplage parfait (théorème de Hall) => il existe une bijection entre les classes de P et de P' qui induit par la construction même du graphe, un système de représentants communs.
Je crois que je vais en rester là, cela me prend trop de temps.
Super, ça marche dans le cas fini !
cf mes précédents messages.
Je crois que je vais en rester là, cela me prend trop de temps.
Je répondrai ici pour de futures nouvelles pistes. Tu regarderas quand tu voudras/pourras
Bonjour Foxdevil,
Merci. N'hésite pas à venir poster ici pour de nouveaux développements, cela m'intéressera !
Bonsoir coa347,
Alors je suis en vacances du coup c'est un peu galère d'écrire de mon smartphone (Latex devient vite imbuvable sur mobile 
). D'où de nombreux points que j'ai laissé en suspens.
Je reviendrai dessus plus tard.
Pour l'heure (pas de vacances pour les maths ), je viens de me rendre compte d'une conséquence assez étonnante du théorème de Hall:
Ayant le même nombre de classes, on est pas obligé d'avoir le même nombre de d'éléments par classe. Même avec des partitions inégales (mais toujours toutes les deux de même cardinal), on a certains cas où il existe quand même un couplage parfait (et donc un système de représentants des deux classes).
Pour toute partie X de P, les éléments de X sont reliés à au moins autant d'éléments de P' qu'en comporte X (cela parait assez évident, mais cela se voit pour des raisons de même cardinalité entre les classes).
Et effectivement, la cardinalité fait qu'une sous partie X de P aura nécessairement Card(X) sommets adjacents de P' (si ce n'est pas le cas, la construction du graphe fait que X serait inclus dans une union de classes de P' de cardinal inférieur strictement à card(X), ce qui est absurde car on aurait
Quand il n'y a que deux classes, le dénombrement du nombre minimum de systèmes communs de représentants s'obtient assez facilement: \dfrac{n^2}{2} pour n pair, \dfrac{n^2+1}{2} pour n impair (pour un ensemble à n éléments).
Quand il y a plusieurs classes et que n = m (nombre de classes = nombre d'éléments par classe) aussi : c'est n!.
Sinon le dénombrement général me paraît hardcore. J'obtiens une formule inutilisable (et contrairement à ce que je pensais, le nombre de couplages parfaits n'aide pas).
Mais on a la formule:
Enfin je ne lâche pas la solution avec les groupes
. Je me demande, étant donné un ensemble fini avec deux partitions pareilles, à quelles conditions peut-on munir cet ensemble d'une loi dont les classes à gauche et à droite sont ces partitions.
Alors on doit avoir une classe identique dans les deux partitions. Mais encore?
Autre chose. Compter le nombre de systèmes de représentants pour un groupe me paraît intuitivement bien plus atteignable.
Bonjour Foxdevil,
Enfin je ne lâche pas la solution avec les groupes
. Je me demande, étant donné un ensemble fini avec deux partitions pareilles, à quelles conditions peut-on munir cet ensemble d'une loi dont les classes à gauche et à droite sont ces partitions.
Alors on doit avoir une classe identique dans les deux partitions. Mais encore?
Autre chose. Compter le nombre de systèmes de représentants pour un groupe me paraît intuitivement bien plus atteignable.
C'est une question intéressante, je me la suis posée aussi. Je pense que tu veux dire "avec deux partitions différentes, qui comportent une classe commune". La question est : deux éléments dans la même classe à gauche (autre que la classe commune) peuvent-ils être dans la même classe à droite ? Je n'ai en tête que des exemples où ce n'est pas le cas.
Pour le nombre de systèmes communs de représentants, cela parait facile.
Mais on n'a pas la généralité.
Par contre je n'ai pas bien saisi. Tu pourrais détailler plus stp?
Je n'ai rien démontré. Il me semble que le nombre minimum de systèmes communs possibles de représentants est obtenu par le plus grand "mélange" possible des classes (à démontrer).
Puis pour dénombrer, j'ai raisonné par transpositions : quand les deux partitions sont égales, de P à P, il y a n^m systèmes communs de représentants ; chaque transposition (pour aller de P à P') détruit des systèmes.
Pour deux classes, on distingue n pair ou impair ; le plus grand mélange possible est obtenue par la transposition de n/2 éléments (si n pair) ou de (n-1) éléments (si n impair) d'une classe à l'autre.
Pour n classes de n éléments, le plus grand mélange possible est obtenu par des classes de P' composées de n éléments pris chacun dans chacune des n classes de P.
Pour composer un système de représentants, on prend un élément dans une classe (n possibilités), un deuxième dans une autre classe (reste n-1 possibilités), etc ...
Prendre un exemple est le mieux.
Là aussi, cela reste à démontrer.
Le dénombrement général me parait aussi très difficile, mais pas infaisable.
Heu si, dans le cas d'un groupe, deux éléments qui commutent se situent dans les mêmes classes à gauche et à droite. Mais s'ils ne commutent pas, rien ne dit pour l'instant qu'ils ne peuvent pas se situer dans les mêmes classes.
Je détaille un peu pour le minimum de systèmes communs de représentants pour un ensemble de 2 classes à n éléments (et pas un ensemble à n éléments comme je l'ai écrit plus haut) :
- pour n pair, on a systèmes communs de représentants (nombre maximum - ceux éliminés par les transpositions qui échangent la moitié des éléments d'une classe sur l'autre ).
- pour n impair, c'est (nombre maximum - ceux éliminés en échangeant n-1 éléments d'une classe sur l'autre).
Le plus dur me semble de montrer que le minimum est atteint ainsi.
Bonjour Foxdevil,
c'est toujours ... échangeant (n-1)/2 éléments (ou (n+1)/2 ce qui revient au même) ... rrrr.
Sinon, j'ai réfléchi (très rapidement) à la généralisation, il me semble qu'il faut distinguer n>m et n<m (m classes de n éléments). Je ne m'y lance pas.
Il y a peut-être une autre méthode. Mais dans tous les cas, il faut distinguer des cas.
Bonsoir,
Une idée m'est venue (sans y penser) pour le cas général. On place les éléments de la partition P dans un tableau n x m (n lignes, qui représentent les classes, de m éléments).
Le plus grand "mélange" possible des classes est obtenu intuitivement en rangeant dans un (autre) tableau n x m, les éléments qui sont rangés ligne par ligne pour P, colonne par colonne en suivant pour P'.
Il s'agit alors de dénombrer le nombre de n-uplets constitués d'éléments figurant à la fois sur chaque ligne des deux tableaux.
Exemple :
1-2-3-4-5
6-7-8-9-10
11-12-13-14-15
devient :
1-4-7-10-13
2-5-8-11-14
3-6-9-12-15
Le représentant (3-7-14) est obtenu car , et 3, 7 et 14 ne sont pas congrus 2 à 2 modulo 3.
Le représentant (1, 7, 11) est éliminé car 1 congru à 7 modulo 3.
C'est l'idée. Il ne reste plus qu'à la faire aboutir.
Bonjour Foxdevil,
Déjà cela fournit la démonstration cherchée (en ayant démontré, ce qui me parait de loin le plus dur, que cette situation correspond bien au minimum du nombre de systèmes communs de représentants) :
Pour n et m des entiers, il existe toujours m nombres entiers non congrus 2 à 2 modulo n, pris chacun dans un des intervalles [1, n], [n+1, 2n], [2n+1, 3n], ... [(m-1)n+1, mxn].
Bon je vais m'arrêter là, je pense qu'en cherchant bien sur internet, la formule générale du nombre minimum de systèmes communs de représentants doit bien exister quelque part.
Oui bon, on n'a même pas besoin de s'embêter avec ça :
(en ayant démontré, ce qui me parait de loin le plus dur, que cette situation correspond bien au minimum du nombre de systèmes communs de représentants
En effet, en partitionnant l'intervalle d'entiers [1,mxn] en m ensembles de n éléments, on trouve toujours m éléments pris chacun dans chacun des ensembles, non congrus 2 à 2 modulo n.
Donc c'est démontré avec les dénombrements.
Bonjour coa347,
Oups, encore une erreur, c'est n éléments non congrus 2 à 2 modulo n. Bon, je laisse tomber.
Je te comprends parfaitement.
Je m'y penche très prochainement
J'y ai un peu réfléchi, mais pas assez pour dire quelque chose d'intéressant. Dès que j'ai un peu éclairci tout ça, je reposte...Bonsoir coa347,
Donc je m'y suis penché un peu plus.
Déjà pour le théorème de Hall appliqué à une partition finie mais dont les ensembles sont infinis, il y a un détail à corriger: on n'a pas forcément de couplage parfait.
Prendre par exemple l'ensemble , la partition
, où
,
et
, ainsi que la partition
, où
,
et
.
On ne peut pas avoir de couplage parfait.
Ainsi il faut vraiment voir comment le Théorème de Hall tranche au cas par cas quand on est infini (même pour une partition finie).
Ensuite pour le cas d'une partition infinie, on utilise le même exemple que celui du document (le "playboy") pour voir qu'il n'y a pas nécessairement de couplage parfait et que seule la généralisation de Hall permet de trancher au cas par cas.
Sur , considérer la partition
;
....
... ainsi que la partition
;
;
;....;
...
Il est facile de voir que le "playboy", , "gêne" pour réussir à former un couplage parfait. On peut le démontrer rigoureusement, en utilisant le critère fournit dans le document. On obtient bien que ces partitions ne peuvent donner lieu à un couplage parfait (bien qu'étant de même cardinal).
Enfin, pour compter le nombre de systèmes de représentants quand on est dans un Groupe G (fini) avec ses n classes à droites et ses n classes à gauche, on a le fait qu'un ensemble de chaque partition est le même: le sous-groupe H. Donc chaque couplage parfait lie nécessairement H de la première partition (droite) au H de la deuxième partition (gauche) (par définition d'une partition, son intersection avec un quelconque des autres ensemble de la partition sera vide). En utilisant la formule que j'ai citée avant, on en conclut que le nombre de systèmes de représentants (appelons le ) est divisible par le cardinal de H.
De plus on peut encadrer ce nombre (peut être plus finement que je l'ai fait) par:
,
étant le cardinal de l'ensemble des couplages parfaits "convenables".
étant le cas où les classes à droite et à gauche coïncident, i.e. H est normal.
Donc on peut dire que c'est un multiple de |H| compris entre ces deux valeurs. La valeur minorante me paraît assez "grossière" (il faut supposer que les intersections sont toutes de cardinal 1, excepté évidemment celle de H avec H - ce qui intuitivement paraît assez peu possible...). On doit donc pouvoir faire beaucoup mieux...
Sinon, pour revenir à l'horrible formule de calcul de systèmes de représentants dans le cas général, la notion est en fait lié au calcul du permanent 
. Ce qui pour le moment, me paraît bof bof à calculer....à vrai dire je ne vois pas comment même on pourrait la transformer...ni même vers quoi on pourrait bien aller, car tel quel les partitions peuvent donner tout et n'importe quoi et ça me paraît vraiment trop général pour en tirer quoi que se soit.
Je pense que tu veux dire "avec deux partitions différentes, qui comportent une classe commune".
J'avoue que je n'ai pas trop suivi ton raisonnement (mon cerveau est encore en vacances
). Qu'appelles-tu "mélanges"? Pourrais-tu plus expliciter le tout (les calculs aussi) s'il te plaît? Car la je ne vois vraiment pas 
....
Le représentant (3-7-14) est obtenu car 3 \in [1,5], 7 \in [6,10], 14 \in [11,15], et 3, 7 et 14 ne sont pas congrus 2 à 2 modulo 3.
Le représentant (1, 7, 11) est éliminé car 1 congru à 7 modulo 3.
)....Bonjour Foxdevil,
Qu'appelles-tu "mélanges"?
Tout est là : la difficulté à définir ce qu'est un "mélange" des classes est à la hauteur de la difficulté à trouver la formule qui donne le nombre minimum de systèmes communs de représentants.
Plus les classes de P' sont "mélangées" par rapport à celles de P, plus cela détruit des systèmes communs, car deux éléments qui auraient pu fournir (appartenir à) un système commun, ne le peuvent plus dès qu'ils sont dans deux classes différentes de P et dans la même classe de P', ou ne le peuvent pas dès qu'ils sont dans la même classe de P et dans deux classes différentes de P'.
A la limite, avec n=m, si P=P', on a n^n systèmes communs (le maximum), et si P et P' sont complétement mélangés (tous les éléments dans les mêmes classes de P se retrouvent dans des classes différentes de P' : c'est possible car n=m), alors on n'a plus que n! systèmes communs.
Donc le nombre de systèmes communs navigue entre les deux (pour n=m, cas le plus simple).
Je reviendrai sur mes congruences plus tard, mais je sens que là est la clé pour formaliser le dénombrement (peut-être à tort) , par contre, définir le "mélange" de deux partitions me parait très difficile, et au fond il me parait revenir à déterminer leur nombre de systèmes communs de représentants, et il se traduit par ce nombre.
Tout est là : la difficulté à définir ce qu'est un "mélange" des classes est à la hauteur de la difficulté à trouver la formule qui donne le nombre minimum de systèmes communs de représentants. Oui, en effet. J'ai essayé d'y réfléchir, mais je ne vois même pas ce que pourrait être la nature de ce "mélange" (un nombre, un vecteur,...? )
C'est un objet mathématique qui doit décrire à quel point deux partitions se "ressemblent" et aussi contenir l'information de tous les couplages parfaits possibles.
Annuler
connectez vous
algèbre en post-bac