Combien de configurations de liens ?

Calembour

Soit $E$ un ensemble fini à $n$ éléments. Une configuration de liens de $E$ est un ensemble de sous-ensembles de $E$. On dit que deux éléments $x,y$ de $E$ sont liés par une configuration $\Phi$ si il existe dans $\Phi$ un sous-ensemble $\Delta$ tel que $x \in \Delta$ et $y \in \Delta$. Et on dit que $x,y$ sont liés dans $E$ de manière unique par $\Phi$ si il n'existe qu'un unique sous-ensemble dans $\Phi$ contenant à la fois $x$ et $y$.

Exemple : 
$E = \{x,y,z \}$ alors $\Phi_1 = \{ \{ x,y \} \}$ est une configuration où $x$ et $y$ sont liés de manière unique et $y$ et $z$ ne sont pas liés ni même $x$ et $z$. $\Phi_2 = \{ \{x,y \}, \{ y,z \} \}$ est encore une configuration de liens de $E$ où $x$ et $y$ sont liés de manière unique et $y$ et $z$ aussi mais pas $x$ et $z$. $\Phi_3 = \{ \{ x,y \}, \{ x,y,z \} \}$ est encore une configuration de liens de $E$ où $x$ et $y$ sont liés mais pas de manière unique puisqu'ils apparaissent dans l'ensemble à $2$ éléments mais aussi dans l'ensemble à $3$ éléments, mais $x$ et $z$ et $y$ et $z$ sont liés de manière unique. $\Phi_4 = \{ \{ x,y \}, \{ y,z \}, \{ x,z \} \}$ est une configuration de liens où tout le monde est lié de manière unique. $\Phi_5 = \{ \{ x,y,z \} \}$ tout le monde est aussi lié de manière unique ici. 

Question : Existe-t-il un moyen de dénombrer les configurations de liens d'un ensemble fini de cardinal $n$ (donc les ensembles $\Phi$ comme présentés ci-dessus) qui vérifient la condition suivante : tous les éléments sont liés de manière unique entre eux ?

Calembour

Autre point de vue : 

Dans un graphe chaque arête lie seulement deux sommets. Mais dans un hypergraphe chaque arête peut relier un nombre arbitraire de sommets.
On dit qu'un hypergraphe est complet si il existe exactement une seule arête qui relie deux sommets entre eux (comme pour les graphes).

Pour les graphes, on ne prend en compte que les arêtes classiques. Donc si on prend un graphe à $n$ sommets (cela revient à prendre un ensemble à $n$ éléments), alors il n'existe qu'un seul graphe complet, qui se traduit en termes d'ensembles (par rapport au message ci-dessus) comme le sous-ensembles contenant toutes les paires d'éléments (vu qu'une arête dans un graphe ne relie que deux sommets, ça revient à dire qu'une arête est représentée par une paire d'éléments).

Par exemple pour l'ensemble $E = \{ 1,2,3 \} $ à $3$ éléments (qui représente les sommets du graphe), la configuration de liens : $\{ \{1,2\} , \{1,3 \} , \{2,3 \} \}$ est celle correspond au graphe complet à $3$ sommets (il n'y en a qu'un).

Lorsqu'on ouvre la possibilité aux hypergraphes, on obtient alors des sous-ensembles qui peuvent contenir plus que deux éléments. Et la condition de complétude d'un (hyper)graphe est exactement la condition évoquée plus haut : toute paire de sommet doit être reliée par une seule arête. C'est-à-dire qu'il ne doit exister qu'un seul  sous-ensemble $\Delta$ tel que $x \in \Delta$ et $y \in \Delta$ pour toute paire d'élément $x,y$ de l'ensemble.

$$ \forall x,y \in E, \exists ! \Delta \in \Phi, x \in \Delta, y \in \Delta $$

Pour les graphes classiques il n'y a qu'une seule manière de construire un graphe complet. Mais pour les hypergraphes il y a plusieurs manières et il s'agit d'essayer de dénombrer ces manières 

depasse

N'est-ce-pas le nombre de partitions d'un ensemble de cardinal $\binom {n}{2}$?

Calembour

depasse a dit :

N'est-ce-pas le nombre de partitions d'un ensemble de cardinal $\binom {n}{2}$?

il me semble que ce résultat fonctionne

merci!

LOU16

Bonjour,

Je ne comprends vraiment plus rien et dois avoir besoin de bonnes lunettes, car tout ce que je vois, pour les cas $n=3$ et $n=4$, c'est:

Si $E =\{x,y,z\}:\quad\Phi_1=\{ xyz\},\quad \Phi_2 =\{xy,yz,xz\},\:$  

Si $E=\{x,y,z,t\}:\:\:\Phi_1=\{xyzt\},\:\Phi_2=\{xyz,tx,ty,tz\}, \: \Phi_3=\{xyt, zx,zy, zt\},\:\Phi_4=\{xzt, yx,yz,yt\},\:$   $\Phi_5=\{yzt,xy,xz,xt\},\quad \Phi_6=\{xy,xz,xt,yz,yt,zt\},\:$ et nulle part des partitions d'ensembles de cardinal $3$ ou $6$,qui sont respectivement au nombre de $5$ et de $203$.

On ne pêche apparemment pas les mêmes poissons.

Calembour

LOU16 a dit :

Bonjour,

Je ne comprends vraiment plus rien et dois avoir besoin de bonnes lunettes, car tout ce que je vois, pour les cas $n=3$ et $n=4$, c'est:

Si $E =\{x,y,z\}:\quad\Phi_1=\{ xyz\},\quad \Phi_2 =\{xy,yz,xz\},\:$  

Si $E=\{x,y,z,t\}:\quad\Phi_1=\{xyzt\},\:\Phi_2=\{xyz,tx,ty,tz\}, \: \Phi_3=\{xyt, zx,zy, zt\},\:\Phi_4=\{xzt, yx,yz,yt\},\:\\\Phi_5=\{yzt,xy,xz,xt\},\quad \Phi_6=\{xy,xz,xt,yz,yt,zt\},\:$ et nulle part des partitions d'ensembles de cardinal $3$ ou $6$,qui sont respectivement au nombre de $5$ et de $203$.

On ne pêche apparemment pas les mêmes poissons.

Effectivement ce matin je n'ai pas eu le temps de vérifier mais l'idée de @depasse avait l'air de fonctionner

Voici donc les premiers cas :

Cas $n = 3$ :
$E = \{1,2,3 \}$
$2$ Solutions :
$\Phi_1 = \{ \{1,2,3 \} \}$
$\Phi_2 = \{ \{1,2 \} , \{1,3 \}, \{2,3 \} \}$

Cas $n = 4$ :
$E = \{1,2,3,4 \}$
$6$ Solutions :
$\Phi_1 = \{ \{1,2,3,4 \} \}$
$\Phi_2 = \{ \{1,2,3 \}, \{4,1 \}, \{4,2 \}, \{4,3 \} \}$
$\Phi_3 = \{ \{1,2,4 \}, \{3,1 \}, \{3,2\}, \{3,4 \} \}$
$\Phi_4 = \{ \{1,3,4 \}, \{2,1\},  \{2,3 \}, \{2,4 \} \}$
$\Phi_5 = \{ \{2,3,4\}, \{1,2 \}, \{1,3\}, \{1,4 \} \}$
$\Phi_6 = \{ \{1,2\}, \{1,3 \}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\} \}$

Cas $n = 5$:
$E = \{1,2,3,4,5 \}$
$43$ Solutions :
$\Phi_1 = \{ \{1,2,3,4,5 \} \}$
$\Phi_2 = \{ \{1,2,3,4 \}, \{5,1\}, \{5,2\}, \{5,3 \}, \{5,4\} \}$
$\Phi_3 = \{ \{1,2,3,5 \}, \{4,1 \}, \{4,2 \}, \{4,3 \}, \{4,5 \} \}$
$\Phi_4 = \{ \{1,2,4,5 \}, \{3,1 \}, \{3,2\}, \{3,4\}, \{3,5 \} \}$
$\Phi_5 = \{ \{1,3,4,5 \}, \{2,1 \}, \{2,3\}, \{2,4\}, \{2,5\} \}$
$\Phi_6 = \{ \{2,3,4,5 \}, \{1,2\}, \{1,3\}, \{1,4 \}, \{1,5\} \} $
$\Phi_7 = \{ \{1,2,3 \}, \{1,4,5\}, \{2,4 \}, \{2,5\}, \{3,4 \}, \{3,5\} \}$
$\Phi_8 = \{ \{1,2,3 \}, \{2,4,5 \}, \{1,4\}, \{1,5\}, \{3,4\}, \{3,5\} \}$
$\Phi_9 = \{ \{1,2,3 \}, \{3,4,5 \}, \{1,4 \}, \{1,5\}, \{2, 4\}, \{2,5\} \}$
$\Phi_{10} = \{ \{1,2,3 \}, \{1,4 \}, \{1,5\}, \{2,4 \}, \{2,5\}, \{3,4 \}, \{3,5\} \}$
$\Phi_{11} = \{ \{1,2,4\}, \{1,3,5\}, \{2,3\}, \{2,5\}, \{4,3\}, \{4,5\} \}$
$\Phi_{12} = \{ \{1,2,4\}, \{2,3,5\}, \{1,3\}, \{1,5\}, \{4,3\}, \{4,5\} \}$
$\Phi_{13} = \{ \{1,2,4\}, \{4,3,5\}, \{1,3\}, \{1,5\}, \{2,3\}, \{2,5\} \}$
$\Phi_{14} = \{ \{1,2,4\}, \{1,3\}, \{1,5\}, \{2,3\}, \{2,5\}, \{4,3\}, \{4,5\} \}$
$\Phi_{15} = \{ \{1,2,5\}, \{1,3,4\}, \{2,3\}, \{2,4\}, \{5,3\}, \{5,4\} \}$
$\Phi_{16} = \{ \{1,2,5\}, \{2,3,4\}, \{1,3\}, \{1,4\}, \{5,3\}, \{5,4\} \}$
$\Phi_{17} = \{ \{1,2,5 \}, \{5,3,4\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\} \}$
$\Phi_{18} = \{ \{1,2,5 \}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{5,3\}, \{5,4\} \}$
$\Phi_{19} = \{ \{1,3,4 \}, \{1,2,5\}, \{3,2\}, \{3,5\}, \{4,2\}, \{4,5\} \}$
$\Phi_{20} = \{ \{1,3,4 \}, \{3,2,5\}, \{1,2\}, \{1,5\}, \{4,2\}, \{4,5\} \}$
$\Phi_{21} = \{ \{1,3,4 \}, \{4,2,5\}, \{1,2\}, \{1,5\}, \{3,2\}, \{3,5\} \}$
$\Phi_{22} = \{ \{1,3,4\}, \{1,2\}, \{1,5\}, \{3,2\}, \{3,5\}, \{4,2\}, \{4,5\} \}$
$\Phi_{23} = \{ \{1,3,5\}, \{1,2,4\}, \{3,2\}, \{3,4\}, \{5,2\}, \{5,4\} \}$
$\Phi_{24} = \{ \{1,3,5\}, \{3,2,4\}, \{1,2\}, \{1,4\}, \{5,2\}, \{5,4\} \}$
$\Phi_{25} = \{ \{1,3,5\}, \{5,2,4\}, \{1,2\}, \{1,4\}, \{3,2\}, \{3,4\} \}$
$\Phi_{26} = \{ \{1,3,5\}, \{1,2\}, \{1,4\}, \{3,2\}, \{3,4\}, \{5,2\}, \{5,4\} \}$
$\Phi_{27} = \{ \{2,3,4 \}, \{2,1,5\}, \{3,1\}, \{3,5\}, \{4,1\}, \{4,5\} \}$
$\Phi_{28} = \{ \{2,3,4\}, \{3,1,5\}, \{2,1\}, \{2,5\}, \{4,1\}, \{4,5\} \}$
$\Phi_{29} = \{ \{2,3,4\}, \{4,1,5\}, \{2,1\}, \{2,5\},\{3,1\}, \{3,5\} \}$
$\Phi_{30} = \{ \{2,3,4 \}, \{2,1\}, \{2,5\}, \{3,1\}, \{3,5\}, \{4,1\}, \{4,5\} \}$
$\Phi_{31} = \{ \{2,3,5 \}, \{2,1,4\}, \{3,1\}, \{3,4\}, \{5,1\}, \{5,4\} \}$
$\Phi_{32} = \{ \{2,3,5 \}, \{3,1,4\}, \{2,1\}, \{2,4\}, \{5,1\}, \{5,4\} \}$
$\Phi_{33} = \{ \{2,3,5 \}, \{5,1,4\}, \{2,1\}, \{2,4\}, \{3,1\}, \{3,4\} \}$
$\Phi_{34} = \{ \{2,3,5\}, \{2,1\}, \{2,4\}, \{3,1\}, \{3,4\}, \{5,1\}, \{5,4\} \}$
$\Phi_{35} = \{ \{2,4,5\}, \{2,1,3\}, \{4,1\}, \{4,3\}, \{5,1\}, \{5,3\} \}$
$\Phi_{36} = \{ \{2,4,5\}, \{4,1,3\}, \{2,1\}, \{2,3\}, \{5,1\}, \{5,3\} \}$
$\Phi_{37} = \{ \{2,4,5\}, \{5,1,3\}, \{2,1\}, \{2,3\}, \{4,1\}, \{4,3\} \}$
$\Phi_{38} = \{ \{2,4,5\}, \{2,1\}, \{2,3\}, \{4,1\}, \{4,3\}, \{5,1\}, \{5,3\} \}$
$\Phi_{39} = \{ \{3,4,5\}, \{3,1,2\}, \{4,1\}, \{4,2\}, \{5,1\}, \{5,2\} \}$
$\Phi_{40} = \{ \{3,4,5\}, \{4,1,2\}, \{3,1\}, \{3,2\}, \{5,1\}, \{5,2\} \}$
$\Phi_{41} = \{ \{3,4,5\}, \{5,1,2\}, \{3,1\}, \{3,2\}, \{4,1\}, \{4,2\} \}$
$\Phi_{42} = \{ \{3,4,5\}, \{3,1\}, \{3,2\}, \{4,1\}, \{4,2\}, \{5,1\}, \{5,2\} \}$
$\Phi_{43} = \{ \{1,2 \}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\} \}$

j'espère ne m'être pas trompé 

Cordialement Calembour

Calembour

doublon

LOU16

Re,

Pour $n=5$, j'aperçois $47$ "configurations" :$\quad1+\binom 5 4+\binom 5 3\times(3+1)+1.$

Calembour

LOU16 a dit :

Re,

Pour $n=5$, j'aperçois $47$ "configurations" :$\quad1+\binom 5 4+\binom 5 3\times(3+1)+1.$

Exact il m'en manque

Peut être pourrait on trouver une formule de récurrence ?

lourrran

Dans ton recensement, le n°16 et le n°27 sont identiques.  Et il y a d'autres doublons.

Tu peux recenser les différentes formes, et compter combien de choix possibles pour chaque forme.
Pour tes 6 première solutions, ok.
Pour la 7ème, c'est {{1,2,3},{1,4,5},{2,4},{2,5},{3,4},{3,5}} 
Si on prend les éléments de cette forme, le 1 joue un rôle très particulier, il y a 5 façons de choisir le nombre qui est commun aux 2 triplets.
Et une fois qu'on a choisi 1, on peut compléter avec (2,3), (2,4) ou (2,5) pour le premier triplet. 
Il y a donc 15 solutions du type (a,b,c)(a,d,e)(b,d)(b,e)(c,d)(c,e)
J'ai l'impression que Lou16 compte 30 au lieu de 15 ici. (a,b,c)(a,d,e)(b,d)(b,e)(c,d)(c,e) fait doublon avec (a,d,e)(a,b,c)(b,d)(b,e)(c,d)(c,e) 
Ta 10ème solution... un triplet, et le reste est 'imposé'. Il y a 10 façons de choisir un triplet parmi 5 éléments. Tu n'en as que 9, il te manque la solution avec le triplet (1,4,5)
Et la dernière solution, que des doubletons, ok.
1+5+15+10+1=32.

depasse

Bonsoir
Mon raisonnement visiblement fallacieux:
Soit
$E$ un ensemble de cardinal $n>1$,
$\Phi (:= \{P_1,P_2,...P_k\})$ un ensemble de parties de $E$ - chacune de cardinal au moins $2$- tel que
toute partie de cardinal $2$ de $E$ soit incluse dans un et un seul des $P_i$. (*)
Pour tout élément $P_i$ de $\Phi$, $\phi (P_i)$ désigne l'ensemble des parties de cardinal $2$ de $P_i$.
Pour que la condition (*) soit remplie, il faut et il suffit que l'ensemble des $\phi (P_i)$ soit une partition de l'ensemble qui est la réunion des parties de cardinal $2$ de $E$, lequel ensemble est de cardinal $\binom{n}{2}$.
@LOU16 et @jandri ont toujours su me remettre sur les rails. A nouveau je compte sur eux (et tous les autres) pour situer mon erreur dont je ne doute pas.
Cordialement
Paul
Edit: j'ai rajouté "qui est la réunion "

lourrran

Je ne vais pas savoir t'aider.

Par contre, j'avance un tout petit peu dans ma réflexion.
On recherche des sous-ensembles de $E$ ($E_i$, $i =1$ à $k$) tels que pour tout couple $i,j$ avec $i \neq j$, l'intersection $E_i \cap E_j$ soit ou bien vide, ou bien réduite à un singleton.
Dès qu'on a trouvé un tel jeu de sous ensembles, on a la base pour une solution, il suffit d'ajouter toutes les paires nécessaires pour que chaque $x_i$ soit relié à chaque $x_j$.
Et pour éviter de compter 2 fois une même solution, on a besoin que tous nos ensembles $E_i$ soient de cardinal au moins égal à 3

Du coup, si on recense toutes les solutions, on peut alléger les notations.
Au lieu d'écrire $\Phi_2 = \{ \{1,2,3,4 \}, \{5,1\}, \{5,2\}, \{5,3 \}, \{5,4\} \}$, on peut parfaitement écrire $\Phi_2 = \{ \{1,2,3,4 \}   \}$ ; les 4 paires nécessaires pour compléter la solution sont sous-entendues.
La dernière décomposition devient : $\Phi_{43} = \{  \}$

J'avais besoin d'écrire noir sur blanc cette reformulation, pour y voir plus clair. A suivre peut-être.

lourrran

Continuons, en cherchant pour les valeurs suivantes de n.
Sauf erreur ou oubli tout à fait possible (et même très probable)
Pour n=6, 
on a :
1 solution de la forme abcdef
6 de la forme abcde
15 de la forme abcd
20 de la forme abc
1 de la forme $\{ \}$
20 de la forme abc,def
60 de la forme abcd,def
90 de la forme abc,cde
Total = 213.

pour n=7
1 solution de la forme abcdefg
7 de la forme abcdef
21 de la forme abcde
35 de la forme abcd
35 de la forme abc
1 de la forme $\{ \}$
35 de la forme abcd,efg
140 de la forme abc,def
105 de la forme abcde,efg
420 de la forme abcd,def
140 de la forme abcd,defg
315 de la forme abc,ade
105 de la forme abc,ade,afg
840 de la forme abc,ade,cef
630 de la forme abc,cde,efg
Total = 2830

LOU16

Re,

Mon décompte de $47$ est en effet erroné.

Pourtant bien repérée dans un premier temps, une "division par $2$ " y est finalement passée à l'as.

C'est bien $1+5+\cancel{30}15+10+1=32.$

lourrran

@depasse
Je pense avoir compris ton raisonnement, et ton erreur.
Regardons $n=5$, et $E=\{a,b,c,d,e\}$
On peut noter $L_E$ l'ensemble des liens de $E$ : $L_E=\{ab,ac,ad,ae,bc,bd,be,cd,ce,de\}$ qui a bien un cardinal de $\binom{n}{2}=10$
Mes notations ne sont pas standard, mais je pense qu'elles sont claires.
Les éléments qu'on cherche sont bien des partitions de $L_E$, oui.
Mais toutes les partitions ne sont pas valides.
Par exemple, pour une partition donnée, si $ab$ et $bc$ sont dans la même classe $\mathcal{C_i}$, alors $ac$ doit aussi être dans cette classe $\mathcal{C_i}$
Cette contrainte élimine beaucoup de partitions. 
En particulier, dans les partitions qui nos intéressent, toutes les classes ont un cardinal qui est un nombre triangulaire.

depasse

Bonjour
Tout à fait, @lourrran et merci: mon $\phi$ d'un $2^n$-ensemble dans un $2^\binom{n}{2}$-ensemble ne saurait être surjectif!
Ce serait miraculeux (?) qu'il le devienne si l'on restreint l'arrivée à la partie du $2^\binom{n}{2}$-ensemble dont les éléments sont de cardinal triangulaire.
Cordialement
Paul

lourrran

Et le miracle ne se produira pas. Pour $n$ petit, on trouve très vite des partitions dont toutes les classes sont de cardinal triangulaire, mais qui ne sont pas conformes. Et donc, a fortiori pour $n$ grand.