# Contractions de remplacement : 8 des 9 patchs établis

Suite de `4CT_admissibilite_contractions.md`, qui établit l'hypothèse 2 du
lemme des contractions (§5 de `4CT_corpus_complet.md`) pour 375 des 384
patchs C avec leur contraction historique. Les 9 autres identifient une
paire de sommets de bord séparée seulement par un quadrilatère. Ce document
les traite en changeant de contraction.

Scripts : `experiments/general_contractions.py` (énumération en C :
`experiments/general_contractions.c` ; outils communs dans
`experiments/alternative_contractions.py`). Résultat dans
`experiments/alternative_contractions_summary.json`, reporté dans
`atlas_data.json` par `experiments/apply_alternative_contractions.py`
(champ `contraction_admissibility.alternative_contraction`, statut
`proven_by_alternative_contraction`).

## Idée

Rien n'oblige à utiliser la contraction historique q. Le lemme des
contractions vaut pour **toute** contraction q' d'arêtes de P qui vérifie
ses trois hypothèses. On cherche donc, pour chacun des 9 patchs, une
contraction q' dont l'hypothèse 2 se démontre par le seul argument du
triangle, et dont l'hypothèse 3 est vraie :

- **groupes connexes** : chaque groupe de sommets identifiés est connexe
  dans P, donc G/q' est obtenu en contractant des arêtes et reste planaire ;
  au moins un groupe a deux sommets, donc G/q' a moins de sommets que G
  (hypothèse 1) ;
- **paires protégées** : deux sommets de bord a, b d'un même groupe sont
  non consécutifs sur le bord et ont un **voisin intérieur commun** u. Une
  arête de H entre a et b fermerait le triangle a–u–b–a. Ce triangle
  traverse le bord en a et en b (les arêtes a–u et u–b sont dans le disque,
  l'arête a–b en dehors), donc il sépare les deux arcs du bord entre a et b,
  tous deux non vides. Ce serait un triangle séparateur, impossible dans un
  contre-exemple minimal (argument démontré dans
  `4CT_admissibilite_contractions.md`). Les sommets
  intérieurs n'ont aucune arête vers H (§2 du corpus complet), et les arêtes
  du bord ne relient que des sommets consécutifs : l'hypothèse 2 est
  établie. Sur les 9 patchs, les paires ainsi protégées sont exactement les
  paires non consécutives ayant un voisin intérieur commun ;
- **hypothèse 3** : aucune coloration de P/q' (le patch contracté) n'induit
  sur le bord un mot résiduel, c'est-à-dire un mot non éliminé par la
  fermeture par échanges. Toute coloration de G/q' se restreint à une
  coloration de P/q', donc son mot de bord n'est pas résiduel et la
  coloration s'étend à P.

Aucune borne sur le nombre d'arêtes contractées n'est nécessaire : la borne
RSST (au plus 4 arêtes) sert à garantir l'hypothèse 2 par la 6-connexité
interne, que l'on n'utilise pas ici.

## Recherche exhaustive

On énumère **toutes** les partitions de V(P) en groupes connexes, non
triviales, dont les paires de bord sont protégées :
- les partitions du bord en blocs de paires protégées deux à deux ;
- tous les **regroupements intérieurs** : chaque sommet intérieur choisit
  un parent parmi ses voisins ou lui-même. Sans cycle, il remonte à un sommet
  de bord ou à une racine intérieure. Toute partition connexe s'obtient ainsi,
  en prenant une forêt couvrante de chaque groupe, enracinée à ses sommets
  de bord ou, s'il n'en a pas, en l'un de ses sommets ;
- pour chaque combinaison, les groupes à plusieurs sommets de bord doivent
  être connexes.

Pour chaque candidat et chaque mot résiduel constant sur les blocs, les
groupes de bord reçoivent leur couleur ; on cherche une coloration des
groupes intérieurs restants (listes puis retour arrière). Le premier mot
réalisé rejette le candidat.

Une première version ne parcourait que les partitions **ancrées**, où
chaque groupe contient un sommet de bord, en supposant qu'en réunir deux ne
fait que retirer des mots réalisés. C'est faux : réunir deux groupes
**adjacents** est une contraction, pas une identification. Un sommet
intérieur qui ne trouvait pas de couleur peut en trouver une en prenant
celle de son voisin. Cette version ne trouvait que 5 patchs ; la recherche
complète en trouve 8. Par exemple, pour 126.8168, la contraction retenue
laisse libres les sommets intérieurs 14, 15 et 17.

**Contrôles.**
- Toute contraction trouvée est réduite (on retire des sommets intérieurs
  tant que les groupes restent connexes et qu'aucun mot résiduel n'est
  réalisé). Elle est ensuite revérifiée en Python sur tout le résidu, par
  deux calculs indépendants : retour arrière sur listes et énumération brute
  de toutes les colorations des sommets intérieurs.
- Pour un échantillon d'un candidat rejeté sur 2 000 (23 239 au total), le
  mot que le programme C dit réalisé est recoloré en Python ; les groupes
  sont revérifiés connexes, et leurs paires protégées.
- 0 écart.

## Les 8 patchs établis

| Patch | Bord | Mots résiduels | Contraction historique | Contraction de remplacement (groupes) | Paires de bord et sommet commun | Traces de bord (directes / par échanges) | Candidats testés |
| --- | ---: | ---: | --- | --- | --- | --- | ---: |
| 128.136 | 11 | 2 020 | 15–12, 1–12, 3–12, 10–15 | {1,10,16} {3,5,13} {6,8,17} | 1–10 via 16 ; 3–5 via 13 ; 6–8 via 17 | 189 (62 / 127) | 46 040 |
| 126.8168 | 12 | 6 863 | 16–17, 6–16, 9–17, 11–17 | {1,11,18} {7,9,13,16,19} | 1–11 via 18 ; 7–9 via 19 | 450 (155 / 295) | 264 762 |
| 8406.123 | 12 | 4 329 | 15–13, 1–13, 3–13, 5–15 | {3,5,14} {7,9,16,17,18,19} {10,12,20} | 3–5 via 14 ; 7–9 via 19 ; 10–12 via 20 | 324 (72 / 252) | 886 613 |
| 140.8406 | 13 | 18 039 | 16–14, 2–14, 4–16, 6–16 | {2,4,15} {6,8,17,20} {14,19} | 2–4 via 15 ; 6–8 via 20 | 1 503 (261 / 1 242) | 1 249 235 |
| 7696.442802 | 13 | 14 084 | 17–14, 1–14, 10–14, 8–17 | {1,3,15} {4,6,21} {8,10,18} {11,13,22} | 1–3 via 15 ; 4–6 via 21 ; 8–10 via 18 ; 11–13 via 22 | 567 (226 / 341) | 5 319 173 |
| 8406.363 | 13 | 14 685 | 16–14, 1–14, 3–14, 5–16 | {1,12,19} {3,5,15} {7,9,17,18,20} | 1–12 via 19 ; 3–5 via 15 ; 7–9 via 20 | 810 (126 / 684) | 1 284 300 |
| 439328.136 | 13 | 14 471 | 19–14, 1–14, 3–14, 12–19 | {1,12,20} {3,5,15,16,17,18} {8,10,21} | 1–12 via 20 ; 3–5 via 15 ; 8–10 via 21 | 648 (143 / 505) | 1 147 791 |
| 7877.442802 | 14 | 47 722 | 17–15, 1–15, 11–15, 4–17 | {1,3,16,17,18} {9,11,19} {12,14,23} | 1–3 via 16 ; 9–11 via 19 ; 12–14 via 23 | 1 350 (711 / 639) | 28 958 035 |

Pour chacun, **0 mot résiduel réalisé**, par les deux calculs. Les traces
de bord sont les mots réalisés par le quotient. Aucune n'est résiduelle :
certaines s'étendent directement à P, les autres après échanges de Kempe.
Les sommets absents des groupes restent seuls. La colonne « candidats
testés » compte les partitions examinées : pour chaque partition du bord,
jusqu'à la première qui convient.

Chaque paire de bord identifiée est à écart 2 le long du bord (1–10 sur
un bord de 11 sommets, 1–11 sur un bord de 12 et 1–12 sur un bord de 13
enjambent le dernier sommet). C'est exactement le type de paire que
l'argument du triangle traitait déjà pour les 375 autres patchs. La
contraction historique de ces 8 patchs identifiait au contraire au moins une
paire à écart 3 à 7, séparée seulement par un quadrilatère.

## Le dernier patch : 126.62942

Bord de 14 sommets, 84 125 mots résiduels. Contraction historique
19–15, 17–15, 1–15, 6–17 : elle identifie 1 et 6 (écart 5). Paires
protégées : 1–13 (via 20), 2–4 (16), 4–6 (17), 8–10 (23), 11–13 (22).
La recherche complète examine 18 partitions du bord et 3 698 312
regroupements intérieurs (22 406 513 choix de parents sans cycle), soit
**7 328 989 contractions candidates : aucune ne convient**. Le programme C
a rejeté chacune sur un mot réalisé, et 3 664 de ces rejets ont été
recontrôlés en Python.

Autrement dit, aucune contraction d'arêtes de P, de n'importe quelle
taille, dont les paires de bord identifiées sont protégées par un triangle,
ne vérifie l'hypothèse 3 pour ce patch. En particulier la contraction de la
diagonale {i, u2} proposée comme « piste ouverte » dans
`4CT_admissibilite_contractions.md` échoue. Il faudra
identifier au moins une paire séparée seulement par un quadrilatère, donc
démontrer qu'un contre-exemple minimal n'a pas de quadrilatère séparateur
de ce type. C'est précisément le résultat cité.

## Réserve

Comme pour les 375 autres patchs, l'argument suppose une **occurrence
fidèle** du patch dans G : les sommets du bord sont distincts dans G, et
les sommets intérieurs n'ont pas d'autres voisins que ceux décrits par P.
C'est la même hypothèse que celle du reste de ce document, pas une
hypothèse nouvelle.