Tournoi tocar-handicappé

Je présise, même si c'est implicite, qu'il faut que $i\to s_i$ soit croissante. Ou de façon équivalente que pour toute $n$-permutation $t$, on ait "la formule que tu as donné"* pour $t(s):=(s_{t(1)},...,s_{t(n)})$.

[edit : marco je n'avais pas bien lu ta formule, elle marche même pour une liste non croissante, d'ailleurs très élégante, je me disais, "tiens il note les entier en majuscule!!" lol]

par exemple $(3,3, 0,0)$ vérifie la formule mais $(0,0,3 ,3)$ n'est pas un score.

*i.e on remplace $j$ par $t(j)$ dans la formule caracteristique du score.
[Comme j'ai mal lu ta formule cette substitution n'y a pas de sens, donc je donne celle que je croyais :

Pour tout $k$ au plus $n$ et tout $t$ permutation, $s_{t(1)}+...s{t(k)}\geq k(k-1)/2$ avec égalité si $k=n$
ce qui est équivalent à ta formule, car les deux sont équivalente au fait de prendre $t$ telle que $s$ soit croissante. C'est le cas (le cas croissant) le plus difficile à valuder la formule il implique tous les autres. Cette remarque est importante puisque, un TH est un tournois muni d'une indexation.]

Je propose d'appeler "scoring" n'importe quel $t(s)$ lorsque $t$ parcourt $S_n$, et pas necessairement croissant. Pour tout scoring il existe au moins un tournois indexé (et au plus un tournois TH!) qui ait ce scoring. Je continue dans un autre message car je ne vois plus rien (car depuis mon téléphone, comme dirait cc^^)

Disons qu'une n-liste d'entiers relatifs $(p_1,...,p_n)$ est un "parenthésage" si pour tout $k\leq n$ on a $p_1+p_2...+p_k\geq 0$ avec égalité si $k=n$. Si on a egalité ssi $k=n$ on dira qu'il est indécomposable.

$L$ et $L'$ sont des n-listes P-équivalentes (P pour parenthésage) ssi il existe une n-permutation $t$ telle que $t(L+\Delta_n)= L'+\Delta_n$ oú $\Delta_n=(0,1,2,...n-1)$, c'est à dire quand on ajoute $\Delta_n$ on a les même termes à permutation près (la notation $t(Liste)$ est définie dans le post au dessus pour les scores mais s'étend évidemment à n'importe quelle n-liste.

Un parenthesage $P$ sera dit universel si tous les éléments de sa P-classe sont des parenthèsages autrement dit, si $P+\Delta$ est un scoring. (je ne mets plus les $n$ au Delta quand il n'y a pas d'ambiguité).

On dira que le parenthésage $P=(P_1,...P_n)$ est monotone si $P+\Delta$ est un score, c'est à dire un scoring croissant, c'est à dire que $P_{i+1}\geq P_i-1$


Ecriture en base 1 (LOL) des termes d'un parenthésage :
Un nbre positif s'ecrit comme autant de parenthèse ouvrantes consécutives suivie disons d'un 0, et si l'entier est négatif, on l'écrit comme autant de parenthèses fermantes consécutives, précédées d'un 0. On pourrait soit se passer du 0 soit garder un seul autre symbole mais puisqu on représente une liste, on a besoin d'un symbole de séparation :

exemple
scoring (1,1, 1) donne le oarenthèsage en base 1 (000)
scoring (1212) donne (0(00)0)
scoring (0,1,2 3,4) donne 00000

Les parenthèsage associés sont respectivement (1,0,-1), (1,1,-1,-1) et (0,0,0 0,0)

Ceci étant posé, je vais commencer à dire des trucs chouettes : on va pouvoir effectuer des substitutions !!

Remarquons deux choses (il faut un peu se pencher sur le problème mais on s'en convaincra en l'ayant fait)

lemme 1 : Si $P=(P_0,P_1...)$ est le parenthèsage associé à un tournois TH et que $P$ s'annule en $i$, c'est à dire que le $i$-ième terme du scoring associé vaut $i$ (je me rend compte qu'il faut commencer la numérotation à 0, pour ne pas avoir à se trimballer des moins 1), ce qui je le rappelle dans la reoresentation en base 1 (appelons ça" le dessin"), correspond au 0 "tout seul", eh bien on peut substituer à ce 0 tout seul, un autre dessin TH, et on obtiendra....

... pas un dessin de TH, non, raté hinhinhin, mais un score d'un TH, qu'on déduit facilement, Je détaillerai comment si vous voulez mais, bien que pas compliqué , ça demande encore plus de blabla, mais DU COUP....

Réponse : ça ne m'étonnerait pas du tout!

En tout cas on montre (sans trop de difficultés) que les symétriques monotones, unianulés s'obtiennent ainsi...

Il en va de même pour les scores croissant d'au plus 1, on va utiliser une astuce similaire en remarquant qu'un tel score équivalent (si je ne dis pas de bêtise) à un symétrique monotone unianulé (sma) à l'ajout de 0 près (cf. lemme 2)
En fait je crois que les substitution de 0 suivies de parethèse sont aussi bien manipulable que les substitution "libres" et qu'on peut en dire des choses simmilaires, on pourra donc poser une seconde QUESTION encore plus probablement oui-répondable, j'espère que ce deblayage perso en inspirera certains, là je pense ne pas être très loin...

2) est faux : contrexemple 123333

Super idee*

5) pour tout score il existe un tournoi (S, A) et un sous-ensemble propre de sommet P tel que pour toute paire de sommets $a,b\in P$ et tout sommet $c\in S-P$ on a $ac$ <=> $bc$

Ca implique 0) d'après un theorème d'un article de claude quitté dans le post que je vais mettre en lien quand j'aurai l'ordi, qui dit que par une suite de "switch" (inversion des arêtes d'un circuit) appliquées à un tournoi, on peut se ramener à n'importe quel autre tournois de même score.

Du coup pour tout score on trouve un tournois comme dans 5) (supposé contrexemple minimal) on contracte P en un point et on obtient un tournoi Q par construction, stipulée possible par 5).
Par minimalité du contrexemple, on applique à ce tournois Q les switchs qui le transforment en un TH, on pouvait aussi supposer que la restriction de T à P est TH, (par minimalite du contrexemple) , on distribue ensuite tous les switch de Q dans P et on obtient bien un TH, contradiction.

Reste à prouver 5)

*cette immodestie n'est destinée qu'à allerter sur le fait que je suis sur du concret, en fait je ne pense pas vraiment qu'elle est super (message pour l'idée qui a eu la bonté de me traverser : cette modestie n'est destinée qu'à te mettre en valeur, et de toute façon, tu t'en fiches, tu es une idée, tu es bien au dessus de nous autres qui croyons vous avoir eues (même pas vous avoir!) alors que c'est vous qui nous menez en bateau, la preuve je vais encore passer pour un tocar à cause de toi! ... euh, pardonne cette subite et outrecuidante franchise en tout cas s'il te plait ne te venge pas en ne marchant plus)