Une conjecture sur les collections de sous-ensembles


Original: http://www.efgh.com/math/subsets.htm

LOGO

Philip J. Erdelsky
3 septembre 2002

 

 

S’il vous plaît e-mail commentaires, corrections et additions au webmestre à pje@efgh.com.

NOTE: A la recherche de l’Internet a finalement révélé que cette conjecture est vraie et est connu comme le théorème de Sperner.

Voici un problème en combinatoire qui m’a mis sur écoute pendant de nombreuses années. Peut-être un combinatoricist peut résoudre à la fois. Je ne pouvais pas.

Considérons un ensemble fini S de N objets. Une collection sans inclusion est un ensemble C de sous-ensembles de S de telle sorte qu’aucun sous-ensemble de la collection est un sous-ensemble propre de toute autre sous-ensemble de la collection.

Un type de collection sans inclusion est la collection de tous les sous-ensembles d’un seul élément de S. Une autre est la collection de tous les sous-ensembles à deux éléments. Cependant, il ya beaucoup, beaucoup d’autres.

Voici la conjecture: La collection de N / 2 éléments sous-ensembles contient au moins autant de sous-ensembles que toute autre collection sans inclusion. Voici N / 2 est arrondie vers le haut ou vers le bas si N est impair. Il ne fait aucune différence, parce que la taille de la collection est la même dans les deux cas.

Tests Brute-force par ordinateur peut vérifier cette conjecture que pour de très petites valeurs de N. Le nombre de sous-ensembles est P = 2N, et le nombre de collections de sous-ensembles est 2P, qui devient très grande, très rapide!

L’application qui a donné lieu à cette conjecture est probablement obsolète maintenant, mais ici il est. Il y avait quelque chose qui s’appelle une PROM (Programmable Read-Only Memory). Il a été fabriqué contenant tous les zéros. En utilisant une machine spéciale qui a brûlé sélectivement les connexions internes, l’utilisateur peut changer tout à zéro en un, mais pas vice-versa. Cela s’appelait «brûler» la PROM.

Supposons maintenant que chaque mot de la PROM contient N bits. Si vous codez les informations ainsi exactement N / 2 bits de chaque mot sont changés pour des, les informations ne peut être changé et restent valables. Si il ya une collection sans inclusion plus grande que la collection de tous les sous-ensembles N / 2 éléments, il existe un moyen plus efficace pour ce faire.

Comments are closed.