45809 - Faits et Questions sur le Jeu de Frank. (avec P. Gazzano)

P. Gazzano, N. Lygeros

Dans le cas de la coopération, nous avons dans le Jeu de Frank les faits et questions suivants :

Fait 1 : K6 a une obstruction.

La démonstration se fait via la Théorème de Ramsey.

Fait 2 : K7 a deux obstructions.

Construction à la main à partir de K6.

Fait 3 : K8 a trois obstructions.

Construction à la main à partir de K7.

Fait 4 : K9 a 4 obstructions.

Construction via ordinateur.

Fait 5 : K10 a 5 obstructions.

Construction via ordinateur.

Fait 6 : A partir de K11, il apparaît un K3

en tant qu’obstruction.

Fait 7 : K11 a 7 obstructions, K12 a 9 obstructions,

K13 a 11 obstructions.

Les premiers cas sont optimaux.

Question 1 : Si n ≥ 5, existe-t-il un Kn avec n-5 obstructions ?

Question 2 : Ce nombre est-il optimal ?

Question 3 : K n+1 a-t-il seulement une obstruction de plus que Kn ?