L’épistémologie contemporaine de la Théorie de
l’évolution dans l’enseignement secondaire français

 Flips

Nous nous intéressons à présent à la construction de pavages. Il est clair qu’étant donné un zonotope, on peut facilement construire un de ses pavages (en ajoutant les sections successives dans un ordre donné, voir Figure 2.14). Le problème consistant à en construire d’autres peut être abordé par la notion de flips. Un flip est une réorganisation locale de tuiles, permettant d’obtenir un nouveau pavage à partir d’ un pavage existant. Nous les définissons à présent de façon plus précise. FIG. 2.14 – Exemple de construction d’un pavage 2.6.1 Pavages d’un d + 1-zonotope unitaire Considérons un zonotope unitaire de codimension 1 (ainsi D = d + 1). On vérifie facilement qu’un tel zonotope admet deux pavages :  Soit V = (v1,…, vd+1) la suite de vecteurs de V , et p0 la proto-tuile construite avec les d premiers vecteurs : il existe un pavage T avec une tuile t0 de type p0 tel que T + {vd+1,1} soit vide et T − {vd+1,1} = {t0}, et un pavage T ′ tel que T − {vd+1,1} soit vide et T + {vd+1,1} = {t0}. Voir Figure 2.15. FIG. 2.15 – Exemples de flips en dimension 2 et 3 Dans ce qui suit, on considérera arbitrairement l’un de ces pavages comme étant en position haute, et l’autre en position basse. Un flip est le passage d’une position à l’autre. Remarquons que chacun de ces deux pavages est symétrique de l’autre par rapport au vecteur Pd+1 i=1 vi/2. Toutes les tuiles de ces deux pavages sont adjacentes 2 à 2, car deux tuiles quelconques ont exactement d − 1 vecteurs en commun, et les lignes de de Bruijn sont de longueur 2. Les ordres respectifs des tuiles dans les lignes de de Bruijn des deux pavages sont inverses l’un de l’autre. 2.6.2 Espaces de pavages Les pavages de zonotopes unitaires de codimension 1 décrits précédemment apparaissent, translatés, dans des pavages de plus grands zonotopes (au sens des multiplicités associées aux vecteurs, ou de la codimension). Supposons qu’un pavage Tz d’un tel zonotope unitaire apparaisse, translaté d’un vecteur de déplacement v, dans un pavage T d’un zonotope Z (formellement, Tz + v ⊆ T). Alors le pavage T ′ = ((T\(Tz + v)) ∪ (T ′ z + v)) est obtenu de T par un flip géométrique (ici T ′ z est le pavage du support de Tz après le flip). Le type du flip est le type de z, support de Tz. Ce flip est montant si Tz est en position basse, et son opposé est un flip descendant. L’espace des pavages d’un zonotope Z est le graphe symétrique étiqueté dont les sommets sont les pavages de Z, et deux pavages sont liés par une arête s’ils diffèrent d’un flip géométrique. L’étiquette de l’arête est le type du flip (voir Figure 2.16). Les arêtes de l’espace des pavages peuvent être orientées par l’orientation des flips. On peut définir une relation entre pavages de la façon suivante : étant donnés deux pavages T et T ′ , on dira que T ≤flip T ′ s’il existe une suite de flips montants menant de T à T ′ . Il sera montré plus tard que cette relation est effectivement une relation d’ordre, mais ceci n’est pas vrai a priori. 

FLIPS 

Dans ce qui suit, on notera un flip par la suite des indices des vecteurs définissant le (d + 1)-zonotope unitaire support du flip. Notons que la représentation canonique des pavages permet cette étude, la proposition suivante établissant la compatibilité des flips avec les transformations élémentaires. Proposition 2.6.1 Soient T1 et T2 deux pavages d’un même zonotope, et T ′ 1 et T ′ 2 leurs images respectives par une transformation, c’est-à-dire qu’il existe une composition de transformations élémentaires Φpavage telle que T ′ 1 = Φpavage(T1) et T ′ 2 = Φpavage(T2). Si T1 et T2 diffèrent d’un flip, alors T ′ 1 et T ′ 2 aussi. Preuve : Nous avons vu précédemment que l’adjacence de tuiles est conservée par les relations d’équivalences entre pavages. Soit {ti} l’ensemble des tuiles flippées entre T1 et T2. Ces tuiles sont adjacentes deux à deux. Ainsi, leurs images dans T ′ 1 et dans T ′ 2 sont également adjacentes deux à deux. Par définition, le support du flip ne peut être pavé que de deux façons. Ainsi, les pavages T ′ 1 et T ′ 2 diffèrent d’un flip. ¤ Proposition

Deux zonotopes équivalents ont même espace de pavage

Preuve : Nous avons vu précédemment que les pavages de zonotopes équivalents peuvent être mis en correspondance deux à deux, et que la relation de flip est conservée par la relation d’équivalence entre pavages, ce qui donne directement le résultat. ¤ Notons que ce résultat implique que l’étude des cas canoniques se généralise à tous les pavages de zonotopes par les relations d’équivalence. Ceci s’applique en particulier aux résultats de structure. Par ailleurs, un résultat important est que ces flips induisent une connexité de l’ensemble des pavages d’un zonotope pour d = 2, i.e. tous les pavages d’un zonotope de dimension 2 peuvent être déduits de l’un d’entre eux par des suites de flips (voir [Des97, Eln97, Ken93]). Cette question reste ouverte dès la dimension .

Codage de pavages de zonotopes de dimension 2

Nous nous restreignons dans ce chapitre au cas de dimension 2, donc aux pavages de polygones à nombre de côtés pair et à symétrie centrale par des parallélogrammes de côté unitaire. Nous présentons ici un codage de ces pavages par un graphe déduit des relations d’adjacence entre tuiles, et montrons la relation d’équivalence qui lie les deux classes d’objets. 3.1 Préliminaires Nous supposerons dans ce chapitre que les pavages présentés sont canoniques. Etant donnés deux vecteurs v = reiθ et v ′ = r ′ e iθ′ , nous rappelons que v < v′ dans l’ordre naturel si θ < θ′ . Soit V = {v1,v2,…, vD} une famille de D vecteurs du plan non colinéaires deux à deux. On suppose que vi < vi+1 dans l’ordre naturel. Soit M = {m1,m2, …,mD} une famille de D entiers positifs. L’entier mi est la multiplicité de vi . Le 2D-gone (V, M) associé à V et M est la partie du plan affine définie par : (X D i=1 λivi , 0 ≤ λi ≤ mi ,mi ∈ M, vi ∈ V ) Il existe plusieurs définitions équivalentes pour ces objets. Par exemple un 2D-gone peut être vu comme la projection d’un hypercube de dimension D sur le plan. Voir [Zie95] pour plus de détails. Pour D = 2, les 2Dgones sont des parallélogrammes ; pour D = 3 ce sont des hexagones ; pour D = 4 des octogones ; pour D = 5 des décagones, etc. Voir figure 3.1. Etant donné un 2D-gone P associé à (V, M), une proto-tuile de P est un 2D-gone construit sur deux vecteurs de V , chacun avec multiplicité 1. Ainsi, chaque proto-tuile est un parallélogramme défini par deux vecteurs .

CODAGE DE PAVAGES DE ZONOTOPES DE DIMENSION

FIG. 3.1 – Un ensemble de vecteurs et son décagone associé. Les multiplicités respectives sont 2,3,1,1,2 de V , et on ne fera aucune différence entre la proto-tuile en temps que figure et la paire de vecteurs servant à la définir. Finalement, un pavage T d’un 2D-gone P est un ensemble de tuiles (c’est-à-dire de copies de proto-tuiles translatées) qui couvre exactement P et tel qu’il n’y ait aucun recouvrement entre tuiles. Ainsi, T est un ensemble de couples dont la première composante est la paire de vecteurs définissant une proto-tuile, et la seconde est un déplacement. Les translations utilisées dans les pavages de 2D-gones peuvent toujours être représentées comme des combinaisons linéaires de vecteurs de V à coefficients entiers : t = P i tivi , ti étant un entier compris entre 0 et mi . Nous prendrons comme vecteur translation le vecteur des hauteurs canoniques principales, et t sera décrit par un vecteur de dimension D, t = (t1,…, tD) où ti est la hauteur associée à vi . Deux pavages T et T ′ de deux 2D-gones P et P ′ sont équivalents si T = T ′ , où T et T ′ sont vus comme des ensembles de couples. Soient P un 2D-gone, et T un de ses pavages. La i-ème famille de de Bruijn de T est l’ensemble des tuiles de T construites sur le vecteur vi . De plus, chaque famille peut être décomposée en lignes de de Bruijn : la j-ème ligne de la i-ème famille est l’ensemble des tuiles construites avec vi et dont la j-ème composante du vecteur de translation vaut j − 1. Pour des raisons pratiques, nous dirons également que la j-ème ligne de la i-ème famille est la α-ème ligne de de Bruijn, où α = Pi−1 k=1 mk + j, mk étant la multiplicité de la k-ème famille. Nous définissons aussi f(α) comme l’indice du vecteur associé à la α-ème ligne, c’est-à-dire que f(α) est le numéro de la famille contenant la ligne α. Notons que deux lignes appartenant à une même famille n’ont jamais de tuile commune, alors que deux lignes de familles différentes ont exactement une tuile en commun dans le pavage. De plus, chaque ligne partage le pavage en deux parties disjointes. Nous utiliserons ces propriétés classiques (voir [dB81]) dans la suite.