Problème ouvert (combinatoire)

Babcool

Bonjour à tous,

Je viens de m'inscrire sur le forum, car j'ai rencontré il y a quelques temps une suite de problèmes de combinatoire pour laquelle je n'arrive pas à trouver de piste de recherche intéressante.

Le problème résumé est le suivant (voir le pdf joint pour une description bien plus détaillée) :
Je considère un ensemble de n éléments, n paire (voir même n une puissance de 2).
L'objectif est de faire un maximum de bi-partitions de cet ensemble (j'entends par là des partitions en 2 parties) dont les partie sont de même taille et dont les intersections sont de tailles n/4 (quand on prend deux bi partitions,

soit $a_1$ ,$a_2$ la première bi-partition et $b_1, b_2$ la deuxième, alors $|a_1 \cap b_1| = |a_1 \cap b_2| = |a_2 \cap b_1| = |a_2 \cap b_2| = \frac{n}{4}$.

Le pdf fournit propose une hypothèse de solution à ce problème, non complètement démontré. L'ensemble de bi-partition de taille maximal est à priori de taille n-1 si l'ensemble de base à n éléments.

Le problème suivant, et c'est actuellement celui sur lequel je bloque correspond au même problème en assouplissant la contrainte sur les intersections, l'intersection ne doit plus être égale à n/4 mais à n/4 ± d avec d petit devant n (si n = 64 ou 128, d <= 5). La seule manière que j'ai eu de procéder consiste à générer des candidats aléatoire et à construire un ensemble comme cela, mais j'aimerais bien pouvoir trouver une solution plus élégante.

Pdf de description plus formelle du problème


Ps : Pour les fans de graphes, le pdf introduit une réduction du problème a une recherche de clique max dans un graphe représentant les bi-partitions possibles (donc très grand :P) et dont les arêtes sont présentes si l'intersection entre 2 bi-partition nous convient.

aurelpage

Salut,

je te propose la construction suivante, si~$n=2^k$ est une puissance de~$2$. On peut supposer que ton ensemble d'éléments est~$V = \mathbb{F}_2^k$ l'espace vectoriel de dimension~$k$ sur le corps à deux éléments.
Soit~$f : V\to \mathbb{F}_2$ une forme linéaire non nulle. Elle induit une partition~$V = f^{-1}(0)\cup f^{-1}(1)$ où chaque partie a bien~$n/2$ éléments. Il y a~$n-1$ telles formes linéaires (l'espace des formes linéaires est aussi de dimension~$k$, il faut enlever la forme nulle) et il n'y en a pas deux proportionnelles donc on a bien~$n-1$ partitions différentes.
Soient~$f,g$ deux formes linéaires différentes. Les intersections de deux parties sont deux sous-espaces affines non parallèles de dimension~$k-1$, c'est donc un sous-espace affine de dimension~$k-2$ et donc de cardinal~$2^{k-2}=\frac{n}{4}$, ce qui est ce qu'on voulait.

Pour généraliser, tu peux essayer de prendre des polynômes de plus grand degré à la place de formes linéaires. L'estimation des intersections risque d'être plus compliquée et de faire appel à de la géométrie algébrique dont je ne suis pas spécialiste. Demande à un expert s'il pense que ça peut marcher.

Aurel

aurelpage

Je viens de chercher un peu, pour le cas plus général tu pourras certainement tirer quelque chose des bornes de Lang-Weil http://terrytao.wordpress.com/2012/08/31/the-lang-weil-bound/

Babcool

Merci beaucoup pour cette réponse (j'arrive un peu tard par contre peut-être). Je vais regarder ça avec attention

Pour ce que j'ai pu lire pour l'instant, je crois que ça dépasse mon niveau de math, mais je devrais pouvoir en discuter sous peu avec un ami qui pourras possiblement éclairer un peu mes lanternes ^^

Edit: Je profite de ce message pour demander au cas où des explications sur les limites de Lang-Weil, car j'ai bien essayé de lire un peu ce qui était dit sur le site indiqué, mais je ne vois pas encore du tout comment je peux utiliser ça dans le cadre de mon problème, et surtout est ce que ça fournit un possibilité de construire les partitions ou simplement de les dénombrer?

Merci d'avance

aurelpage

Salut,

Tout ce que je t'ai donné sert uniquement à construire des partitions, mais pas à compter les partitions possibles.

Commence par digérer la version avec les formes linéaires, on rediscutera de l'autre partie ensuite ;-)

Aurel

Babcool

Salut,

Me voilà de retour, et c'est bon, pour les formes linéaires, j'ai compris comment on pouvait construire l'ensemble des partitions.

Donc, en supposant n = 8, soit $2^3$, on construit les 7 formes linéaires possibles, non proportionnelles 2 à 2, puisque différentes. Chacune fournit la moitié de la bi-partition avec son noyau, et à priori, on est bon. Ça laisse entendre que même en dimension plus haute, c'est facile de construire le noyau de toute forme linéaire, mais ça doit effectivement se faire vite à base d'un peu d'énumération .

Il me semble que je suis à peu près prêt pour l'étape suivante, qui me semble pour l'instant encore obscure. A ce que j'ai compris du survol du post (donc léger :P) et ce que j'ai intuité après la première étape des formes linéaires (donc surement en partie faux xD), le principe consiste à construire des ensembles de polynomes, dont le noyau a une certaine taille (n/2 dans notre cas) et dont les intersections entre leurs noyaux restent à l'interieur de certaines limites (ce qui correspondrait justement au delta que je voudrais permettre pour élargir les possibilités).

Après, ça reste plutôt obscure, autant au niveau de la construction des polynomes, que du calcul de leurs noyaux (et je parle pas de la démonstration de la validité du tout, mais je doute que mon niveau en math me permette d'aller jusque là :P, et puis, je suis informaticien, alors si j'aboutis à la fin à un algo qui marche, je serais content déjà ).

En tout cas, déjà merci beaucoup, car ça me fait une démonstration complète de la première partie de mon problème , ce qui est déjà un grand pas en avant .