"Ze evasive conjecture"

christophe c · July 2010

Pour partager une news que je trouve intéressante. J'étais à un diner hier où quelqu'un m'a informé de cette conjecture. J'ai ensuite vérifié sur google, et ça semble effectivement un problème ouvert (et il est rigolo et montre à quel point on est peu de choses)

Soit n un entier. On considère les nombres entier de 1 à n comme les noms des sommets d'un graphe non orienté.

On note T l'ensemble de tous les graphes possibles dont les sommets sont 1,...,n.

On prend une partie A de T. Quand elle a les 2 propriétés suivantes:

1) A est stable par isomorphisme (ie si G est dans A et si H est isomoprhe à G alors H est dans A, pour tous G,H

2) pour tout G dans A, si on rajoute une ou plusieurs arêtes à G, le graphe obtenu est dans A

On dira qu'elle est héréditaire.

Par ailleurs, étant donné A une partie de T, on joue au jeu evasive(A) suivant:

le joueur1 propose à chaque tour un couple (i,j) de (noms de ) sommets différents et le joueur2 répond oui ou non. S'il dit "oui", on considère que le "futur graphe pas encore dévoilé" contient l'arête (i,j) et s'il dit "non" on considère que le futur... ne contient pas (i,j)

Si à la fin de la partie, le joueur1 a joué tous les C_n^2 arêtes possibles alors il a perdu

Sinon, il a le droit de dire "on arrête là" (avant la fin). Il doit proposer une des 2 affirmations: p:= ou bien "le futur graphe est dans A", ou bien "le futur graphe n'est pas dans A". Le joueur2 doit alors jouer un graphe G, compatible avec les réponses qu'il a lui-même fournies (ie il "dévoile le "futur" graphe dont il était question). Si p est vrai alors le joueur1 gagne, et sinon le joueur2 gagne.

Exercice: prouver que si A = ensemble des graphes connexes alors jouer2 a une stratégie infaillible au jeu evasive(A).

[size=large]

Conjecture (evasive conjecture): Pour tout entier n et toute ensemble A héréditaire, le joueur2 a une stratégie infaillible.

[/size]

christophe c · July 2010

oups, j'oubliais une info qui fera plaisir au public habituel du forum: la conjecture est démontrée pour A héréditaire quelconque et pour n entier... premier

christophe c · July 2010

J'ai trouvé un lien: http://tcsmath.wordpress.com/2008/10/23/lecture-7-the-evasiveness-conjecture/

christophe c · July 2010

C'est marrant que ce thème ne suscite pas d'intérêt. Personne n'aime les hypergénéralités "ouvertes"?

Je serais assez preneur de la traduction de la preuve qui se trouve à la fin du lien du post précédent, an anglais (elle fait 10 lignes!!!) histoire de voir en quoi le fait que "n premier" est crucial...

Merci (d'avance X:-( )

Toto.le.zero · July 2010

Ca m'a l'air plutôt intéressant je dois l'admettre... J'ai un peu la flemme de traduire la fin pour toi Christophe, je le ferai demain si j'ai moins la flemme

Mais c'est pas dur à comprendre quand même !

Sylvain · July 2010

Vite fait et sans garantie autre que mon 17 en version anglaise aux écrits du concours :

"Une preuve quand n est premier

Nous terminerons ce cours par une preuve de la conjecture généralisée valide quand n est premier. La preuve fera allusion aux liens avec la topologie à venir dans le prochain cours.

En premier lieu, nous généralisons la preuve que f est évasive quand \# \{ x : f(x)=1 \} est impair. Pour x \in \{0,1\}^n, notons |x| le "poids de hamming" de x, i.e. le nombre de 1 dans x, et pour f: \{0,1\}^n \to \{0,1\}, définissons

\displaystyle \mu(f) = \sum_{x : f(x)=1} (-1)^{|x|}.

Les lecteurs férus de topologie reconnaîtront là-dedans une sorte de caractéristique d'Euler, et ce lien apparaîtra dans le prochain cours. Nous affirmons que si \mu(f) \neq 0, alors f est évasive. Pour s'en rendre compte, notons que \mu(f) = \mu(f|_{x_i=0})-\mu(f|_{x_i=1}). Ainsi si \mu(f) \neq 0, alors l'une des quantités \mu(f|_{x_i=0}) ou \mu(f|_{x_i=1}) est non nulle, donc un adversaire peut continuer de répondre de sorte que \mu(\cdot) \neq 0. Finalement, remarquons que si \mu(f) \neq 0, alors f doit prendre les deux valeurs 0 et 1, donc l'adversaire peut continuer ainsi jusqu'à ce que les n questions soient posées.

Théorème : Supposons n premier. Si f: \{0,1\}^n \to \{0,1\} est monotone, non triviale, et faiblement symétrique, alors f est évasive.

Preuve : Nous allons montrer que \mu(f) \neq 0. D'abord, nous disons que\mathsf{Sym}(f) contient une permutation cyclique. Ecrivons \mathsf{Sym}(f) = U_1 \cup U_2 \cup \cdots \cup U_n, où U_i = \{ \pi \in \mathsf{Sym}(f) : \pi(1) = i \}. Par transitivité, nous avons |U_1|=|U_2|=\cdots=|U_n|, ainsi n divise |\mathsf{Sym}(f)|. Maintenant comme n est premier, par le théorème de Cauchy il existe un élément \sigma \in \mathsf{Sym}(f) d'ordre n (i.e. un n-cycle).

Comme f est non triviale, nous savons que f(\bar 0)=0 et f(\bar 1)=1. Quel que soit x \in \{0,1\}^n avec x \notin \{\bar 0, \bar 1\}, il est clair que lesl n éléments x, \sigma x, \sigma^2 x, \ldots, \sigma^{n-1} x sont distincts, puisque n est premeir. Mais f est invariante sous l'action de \sigma, donc l'ensemble \{ x : f(x)=1\} se partitionne en classes d'équivalence S_1, S_2, \ldots, S_k, \{\bar 1\}, où |S_i|=n pour tout i. Mais cela implique immédiatement que \mu(f) \equiv 1\,(\bmod\, n), ce qui donne \mu(f) \neq 0."

Voilà, une telle traduction n'atteint sans doute pas la qualité de celles de Véronique Bordellès, mais j'ose croire que je fais tout de même un peu mieux que Google...

christophe c · July 2010

Merci infiniment Sylvain, c'est très généreux de ta part!

christophe c · July 2010

Latexification du post de Sylvain:

Nous terminerons ce cours par une preuve de la conjecture généralisée valide quand n est premier. La preuve fera allusion aux liens avec la topologie à venir dans le prochain cours.

En premier lieu, nous généralisons la preuve que f est évasive quand $\# \{ x : f(x)=1 \} $ est impair. Pour $x \in \{0,1\}^n$ , notons $|x| $ le "poids de hamming" de x, i.e. le nombre de 1 dans x, et pour $f: \{0,1\}^n \to \{0,1\}$, définissons

$\displaystyle \mu(f) = \sum_{x : f(x)=1} (-1)^{|x|}. $

Les lecteurs férus de topologie reconnaîtront là-dedans une sorte de caractéristique d'Euler, et ce lien apparaîtra dans le prochain cours. Nous affirmons que si $\mu(f) \neq 0$, alors f est évasive. Pour s'en rendre compte, notons que $\mu(f) = \mu(f|_{x_i=0})-\mu(f|_{x_i=1})$. Ainsi si $\mu(f) \neq 0$, alors l'une des quantités $\mu(f|_{x_i=0})$ ou $\mu(f|_{x_i=1})$ est non nulle, donc un adversaire peut continuer de répondre de sorte que $\mu(\cdot) \neq 0$. Finalement, remarquons que si $\mu(f) \neq 0$, alors f doit prendre les deux valeurs 0 et 1, donc l'adversaire peut continuer ainsi jusqu'à ce que les n questions soient posées.

Théorème : Supposons n premier. Si $f: \{0,1\}^n \to \{0,1\}$ est monotone, non triviale, et faiblement symétrique, alors f est évasive.

Preuve : Nous allons montrer que $\mu(f) \neq 0$. D'abord, nous disons que $\mathsf{Sym}(f)$ contient une permutation cyclique. Ecrivons $\mathsf{Sym}(f) = U_1 \cup U_2 \cup \cdots \cup U_n$, où $U_i = \{ \pi \in \mathsf{Sym}(f) : \pi(1) = i \}$. Par transitivité, nous avons $|U_1|=|U_2|=\cdots=|U_n|,$ ainsi n divise $|\mathsf{Sym}(f)|$. Maintenant comme n est premier, par le théorème de Cauchy il existe un élément $\sigma \in \mathsf{Sym}(f)$ d'ordre n (i.e. un n-cycle).

Comme f est non triviale, nous savons que $f(\bar 0)=0$ et $f(\bar 1)=1$. Quel que soit $x \in \{0,1\}^n$ avec $x \notin \{\bar 0, \bar 1\}$, il est clair que lesl n éléments x, $\sigma x, \sigma^2 x, \ldots, \sigma^{n-1} x$ sont distincts, puisque n est premeir. Mais f est invariante sous l'action de $\sigma$, donc l'ensemble $\{ x : f(x)=1\}$ se partitionne en classes d'équivalence $S_1, S_2, \ldots, S_k, \{\bar 1\}$, où $|S_i|=n$ pour tout i. Mais cela implique immédiatement que $\mu(f) \equiv 1\,(\bmod\, n)$, ce qui donne $\mu(f) \neq 0$."

christophe c · July 2010

Les lecteurs férus de topologie reconnaîtront là-dedans une sorte de caractéristique d'Euler, et ce lien apparaîtra dans le prochain cours. Nous affirmons que si ...

Encore un astuce empruntée aux déterminants :X !

christophe c · July 2010

http://fr.wikipedia.org/wiki/Caractéristique_d'Euler

christophe c · November 2011

Je fais remonter ce fil et je mentionne la conjecture de Hadwiger (qui pour moi est une sinon la conjecture la plus importante des maths: avis personnel) pour que toute personne intéressée puisse avoir sous le nez les deux conjectures (dont je ne prétends pas qu'elles ont à voir l'une avec l'autre).

Soit $G$ un graphe non orienté, donc un couple $G:=(S,A)$ où $A$ est une partie de $Paires(E)$. On appelle "constracté immédiat" de $G$ un graphe $H:=(Z,B)$ obtenu à partir $G$ en prenant deux sommets reliés $(u,v)\in A$ de $G$ et en définissant:

$Z:=(S\setminus \{u,v\})\cup \{S\}$ et $B:=(Paires(Z) \cap A ) \cup \{ \{x,S\} /x\in Z$ et $\exists t\in \{u;v\}: \{x,t\}\in A \}$

(informellement, on transforme une arête a de G en nouveau sommet et toutes les anciennes arêtes qui avaient un sommet en commun avec a deviennent de nouvelles arêtes de H. Plus informellement encore, ça consiste à "ouvrir les frontières entre pays, deux pays frontaliers deviennent un même pays)

On appelle "mineur" de G un graphe qui peut s'obtenir à partir de G par une suite d'opérations consistant à passer à un sous-graphe ou à un mineur immédiat.

La conjecture de Hadwiger dit: [size=large]si un graphe ne peut pas être colorié avec n couleurs alors il contient parmi ses mineurs un graphe isomorphe à $K(n+1):=(n+1,Paires(n+1))$[/size]

(Rappel: $n:=\{p\in \N: n>p\}$)