Cubes partiels : complétion, compression, plongement
Les familles d’ensembles sont des objets fondamentaux des mathématiques discrètes, et plus précisément de la combinatoire. Elles sont aussi très étudiées dans d’autres domaines tels qu’en algorithmique, géométrie discrète, optimisation combinatoire, théorie des graphes, ou encore en apprentissage. Dans ce dernier domaine, ces familles sont appelées classes de concepts. La notion de VC-dimension, introduite par VAPNIK et CHERVONENKIS en apprentissage, peut être vue comme la dimension combinatoire d’une famille d’ensembles. Il est parfois utile de voir une famille d’ensembles comme un sous-graphe d’hypercube, appelé graphe de 1-inclusion [49, 50]. Une classe fondamentale de ces graphes est constituée des graphes de 1-inclusion préservant les distances de l’hypercube. Ces derniers et leurs sous-classes jouent un rôle important dans la théorie métrique des graphes dans laquelle ils sont appelés cubes partiels. Dans cette thèse, nous étudions des classes de cubes partiels de VC-dimension bornée, notamment nous nous intéressons à des questions de mineurs, de complétion et de compression. Bien que la classe des cubes partiels puisse sembler plutôt restreinte, ils contiennent beaucoup de classes de graphes issues de différents domaines de recherche. Pour donner un exemple intuitif, considérons un arrangement d’hyperplans dans R 2 et son graphe de régions comme illustré dans la figure 1. FIGURE 1. – Un arrangement d’hyperplans de R 2 et son graphe de régions. Alors, chaque région (ou sommet de ce graphe) peut être encodée par un vecteur binaire que nous représentons par un {−,+}-vecteur. Le vecteur associé à une région correspond alors à sa position par rapport aux hyperplans, chaque hyperplan ayant un côté positif (« + ») et un côté négatif (« -« ). La distance entre deux sommets est le nombre d’hyperplans séparant 12 les deux régions. Celle-ci coïncide avec la distance de Hamming entre les {−,+}-vecteurs correspondant à ces régions. Cette observation est vraie quelle que soit la dimension et est due à DELIGNE [33, Proposition 1.3] dans un papier de 1972. En toute généralité, les cubes partiels ont été caractérisés à la même période (1973) par DJOKOVIC´ [36] via la convexité de leurs demi-espaces. En particulier, DJOKOVIC´ définit des classes de parallélisme sur les arêtes, dites Θ-classes. Deux arêtes appartiennent à la même Θ-classe si leurs extrémités différent sur la même coordonnée. Sachant que les cubes partiels sont des sous-graphes isométriques d’hypercubes, les arêtes d’une classe de parallélisme sont exactement les arêtes correspondant à une dimension de l’hypercube. Sur la figure 1, chaque arête peut être associée à un hyperplan, et nous représentons les Θ-classes du cube partiel par des couleurs différentes. Un demi-espace de R 2 correspond à un des deux côtés d’un hyperplan donné. Le sous-graphe induit par les sommets d’un même côté d’un hyperplan, i.e., qui sont étiquetés par la même valeur sur la coordonnée associée à cet hyperplan, est appelé un demi-espace du cube partiel. De plus, pour un hyperplan fixé, nous pouvons considérer le sous-graphe induit par les extrémités de ses arêtes restreint à un des deux demi-espaces de cet hyperplan, et le sous-graphe contenant l’ensemble des cellules qu’il traverse. De tels sous-graphes sont respectivement appelés hyperplan et carrière. Ces notions de demi-espace, hyperplan, et carrière sont naturellement généralisables à tout cube partiel. Une caractérisation récursive des cubes partiels via les expansions isométriques a été donnée par CHEPOI [25] et un algorithme de reconnaissance des cubes partiels en temps O(n 2 ) a été proposé par EPPSTEIN [41]. Les sous-classes des cubes partiels ont, par la suite, été étudiées par de nombreux auteurs et sont présentées de façon approfondie dans l’article de synthèse [9] et dans les livres [35, 47, 75]. Une partie des caractérisations des sous-classes des cubes partiels utilise la notion de pc-mineur, une notion de mineurs adaptée aux cubes partiels. Ceux-ci peuvent être obtenus en contractant les arêtes d’une même Θ-classe ou en considérant un demi-espace. Cet outil fondamental a été introduit et étudié par CHEPOI, KNAUER et MARC [28], mais avait déjà été utilisé de façon implicite dans [24, 26]. Les cubes partiels contiennent de nombreuses classes de graphes importantes. Par exemple, les graphes de topes des matroïdes orientés (une généralisation majeure des graphes de régions des arrangements d’hyperplans) sont des cubes partiels. D’autres classes importantes (avec des application en théorie géométrique des groupes, en apprentissage et en combinatoire) sont les graphes médians et les graphes amples. Finalement, une classe plus générale de cubes partiels est celle des graphes de topes des complexes de matroïdes orientés, une généralisation commune de ces trois classes. Dans cette thèse, nous nous intéressons particulièrement à ces classes de cubes partiels. Les cubes partiels amples correspondent aux graphes de 1-inclusion des familles d’ensembles amples [10, 64]. Une inégalité importante en combinatoire, appelée lemme du Sandwich, établit que la taille d’une famille d’ensembles est comprise entre le nombre d’ensembles pulvérisés et le nombre d’ensembles strictement pulvérisés par cette famille. Les familles amples correspondent alors aux familles atteignant la borne supérieure dans le lemme du Sandwich [10, 19, 64, 94]. Cependant, les familles amples ont été introduites dans un contexte géométrique par LAWRENCE [64] lors de ces travaux sur les ensembles convexes intersectant certains orthants de R d et évitant les autres. LAWRENCE les appelle 13 alors “lopsided”. Les familles amples ont par la suite été redécouvertes indépendamment par d’autres auteurs où elles ont reçu différents noms. En particulier, BANDELT et al. [10] les ont appelées “amples” et ont remarqué l’équivalence avec les familles “lopsided”. Disposant de propriétés structurelles très fortes, les cubes partiels amples et leur complexes cubiques ont de nombreuses caractérisations combinatoires, métriques, et géométriques. En particulier, les cubes partiels amples capturent divers objets tels que les familles maximums et les antimatroïdes [40]. Ils contiennent aussi la classe des graphes médians qui est sans doute la classe la plus étudiée en théorie métrique des graphes. Généralisation des arbres et des hypercubes, les graphes médians apparaissent notamment en théorie géométrique des groupes (en tant que 1-squelettes des complexes cubiques CAT(0) [27]) ou en théorie de la concurrence (en tant que domaines des structures d’événements [14]), et possèdent de nombreuses caractérisations [9, 57]. Les familles d’ensembles sont aussi très présentes dans le domaine de la théorie des matroïdes orientés. Ces derniers sont présentés de manière détaillée dans le livre [17]. Les matroïdes orientés ont été introduits par BLAND et LAS VERGNAS [18] et FOLKMAN et LAWRENCE [43] dans les années 1970 pour ajouter la notion d’orientation à l’abstraction des matroïdes. Les matroïdes orientés possèdent une notion de dualité forte et sont caractérisés par de nombreuses axiomatiques. Notamment, un matroïde orienté peut être défini par un ensemble de cocircuits, ou de covecteurs vérifiant plusieurs axiomes. Il peut aussi être déterminé par ses covecteurs maximaux, appelés topes, ou par le graphe de 1-inclusion de ses topes, appelé graphe de topes [13]. Une sous-classe très importante des matroïdes orientés est celle correspondant aux {−,0,+}-vecteurs des régions des arrangements d’hyperplans centraux. Les topes et le graphe de topes du matroïde orienté associés à un tel arrangement correspondent respectivement aux régions encodée par un {−,+}-vecteur, et au graphe de ces régions. Initialement introduit pour étudier ces arrangements, il se trouve que les différentes axiomatiques des matroïdes orientés englobent plus d’objets puisque FOLKMAN et LAWRENCE [43] ont montré une correspondance exacte entre les matroïdes orientés et les arrangements de pseudo-sphères. Les graphes de topes de matroïdes orientés forment une sous-classe riche des cubes partiels [17]. Encore très étudiés de nos jours, ils ont récemment été généralisés par BANDELT, CHEPOI et KNAUER [13]. En effet, les complexes de matroïdes orientés ont été introduits et étudiés par ces auteurs comme une généralisation des matroïdes orientés et des familles d’ensembles amples. Notamment, ils sont définis par une axiomatique très proche de celle des matroïdes orientés. Plus précisément, leur différence réside dans l’assouplissement d’un axiome de symétrie de la définition des matroïdes orientés. Les graphes de topes des complexes de matroïdes orientés peuvent être vus comme des collages particuliers des graphes de topes des matroïdes orientés. De plus, les graphes de topes des complexes de matroïdes orientés sont des cubes partiels [13, 62]. Les familles d’ensembles (en tant que classes des concepts) jouent aussi un rôle très important dans le modèle de VALIANT [91] de l’apprentissage PAC. Le résultat principal de cette théorie est le théorème de VAPNIK et CHERVONENKIS [93] datant de 1972 et liant la complexité de l’apprentissage à la VC-dimension de la classe de concepts. Un autre lien entre l’apprentissage PAC et la VC-dimension est dû à la notion de schéma de compression, introduite par LITTLESTONE et WARMUTH [65] en 1986. De manière informelle, certains problèmes d’ap14 prentissage nécessitent des échantillons de concepts pour apprendre. Lors de la compression, chaque échantillon est compressé en un bien plus petit sous-ensemble. Lors de la reconstruction, ce sous-ensemble permet néanmoins de retrouver un sous-ensemble compatible avec l’échantillon entier (dans les schémas de compression dits propres, le sous-ensemble doit être un concept). L’une des plus ancienne conjecture en théorie de l’apprentissage, posée par FLOYD et WARMUTH [42], consiste à déterminer si toute classe de concepts admet un schéma de compression où chaque échantillon est compressé en un sous-ensemble de taille linéaire en sa VC-dimension. MORAN et YEHUDAYOFF [69] ont montré que toute famille d’ensembles de VC-dimension d admet un schéma de compression étiqueté de taille 2O(d) . De nombreux auteurs se sont penchés sur l’étude des schémas de compression montrant de meilleures bornes dans le cas où nous nous restreignons à certaines familles d’ensembles. Aussi surprenant que cela puisse paraître, les classes des cubes partiels s’avèrent très intéressantes dans ce contexte et font l’objet de divers travaux. En particulier, MORAN et WARMUTH [68] ont établi que toute famille ample admet un schéma de compression de taille sa VC-dimension. RUBINSTEIN, RUBINSTEIN et BARTLETT [86] ont suggéré une approche pour obtenir des schémas de compression. Celle-ci consiste à étendre des classes de concepts vers des classes de concepts admettant des schémas de compression, sans augmenter la VC-dimension ou en s’autorisant une augmentation linéaire en la VC-dimension. En effet, en utilisant le résultat de MORAN et WARMUTH [68], la conjecture serait résolue si toute famille d’ensembles de VC-dimension d pouvait être étendue à une famille ample de VC-dimension O(d).
Notions de base de théorie des graphes
Un graphe (simple) G = (V,E) est constitué de deux ensembles : un ensemble de sommets V et un ensemble d’arêtes E ⊆ V × V . Le graphe G est dit non-orienté si pour tout u, v ∈ V,(u, v) ∈ E ⇔ (v,u) ∈ E. Lorsque pour tout u ∈ V , (u,u) ∉ E, le graphe G est dit sans boucle. Si le nombre de sommets est fini, alors G est dit fini, sinon G est dit infini. Pour un graphe G donné, son ensemble de sommets est noté V (G) et son ensemble d’arêtes est noté E(G). Dans cette thèse nous nous intéressons principalement à des graphes simples finis, non orientés et sans boucles. Une arête e = (u, v) est généralement notée uv (ou de manière équivalente dans le cas non-orienté vu). Les deux sommets u et v sont appelés les extrémités de cette arête. Ces deux extrémités sont dites incidentes à e. 18 Soit G = (V,E) un graphe. Deux sommets u et v sont dits adjacents (ou voisins) si (u, v) ∈ E. Le degré d’un sommet u de G est le nombre d’arêtes incidentes à ce sommet dans G. Autrement dit, le degré de u est exactement le nombre de voisins de u dans G. Deux arêtes distinctes e et f de G sont dites adjacentes si elles ont une extrémité en commun. Un graphe H = (W,F) est un sous-graphe de G si W ⊆ V et F ⊆ E ∩(W ×W ). Le graphe H est un sous-graphe induit de G si pour toute paire u, v de sommets de H, u est adjacent à v dans H si et seulement si u est adjacent à v dans G. Dans ce cas, nous notons H ⊆ G et disons que H est contenu dans G. Si W (V ou F ( E, alors H est un sous-graphe propre de G. Un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Plus précisément, un isomorphisme entre les graphes G = (V,E) et H = (W,F) est une bijection φ : V → W telle que uv ∈ E si et seulement si φ(u)φ(v) ∈ F. Si une telle bijection existe, G et H sont dit isomorphes et nous notons G ‘ H.
Graphes usuels
Nous rappelons ici la définition et la notation de quelques graphes très classiques. Nous en donnons des exemples dans la figure 1.1. Si tous les sommets d’un graphe G sont deux-à-deux adjacents, alors G est dit complet. Un graphe complet sur n sommets est dénoté Kn. Inversement, un ensemble de sommets deux-à-deux non adjacents est appelé un stable (ou ensemble indépendant). Un graphe est dit biparti si nous pouvons partitionner ses sommets en deux stables A et B, i.e., chaque arête a une extrémité dans A et l’autre dans B. Il est dit biparti complet, noté Ka,b, si |A| = a, |B| = b, et chaque sommet dans A est adjacent à chaque sommet de B. Un chemin, noté Pn, est un graphe composé de n sommets distincts {u1,…,un} dont les arêtes sont u1u2,…,un−1un. La longueur d’un chemin correspond à son nombre d’arêtes. Un chemin Pn (de longueur n −1) est souvent noté par sa séquence naturelle de ses sommets : u1,…,un. Les sommets u1 et un sont appelés les extrémités de Pn. Ce chemin est aussi appelé un chemin de u1 à un, ou un (u1,un)-chemin. Le graphe composé d’un chemin P := u1,…,un avec n ≥ 3 et d’une arête unu1 reliant les deux extrémités de P est appelé un cycle. Nous dénotons parfois un cycle par la séquence cyclique de ses sommets (u1,…,un). La longueur d’un cycle correspond à son nombre d’arêtes (ou de sommets). Un cycle de longueur n est appelé un n-cycle et noté Cn. Un graphe G = (V,E) est dit connexe si ∀u, v ∈ V , il existe un (u, v)-chemin dans G allant de u à v. Un sous-graphe connexe maximal de G est appelé une composante connexe de G. Un arbre est un graphe connexe et sans cycle. Une feuille d’un arbre est un sommet de degré 1. Une forêt est un graphe dont chaque composante connexe est un arbre. Un hypercube, noté Qn, est un graphe composé de 2n sommets étiquetés par les nombres binaires de taille n, et deux sommets sont adjacents si leurs étiquettes diffèrent sur exactement une coordonnée. Il est parfois appelé n-cube ou cube n-dimensionnel. Le graphe obtenu en remplaçant chaque arête de G par un chemin indépendant est appelé 19 une subdivision de G. Nous pouvons observer que tous les sommets qui subdivisent une arête, i.e., qui sont sur un de ces chemins indépendants, sont de degré 2. Nous pouvons voir la subdivision d’un graphe comme le résultat de l’ajout d’un ou plusieurs sommets sur une ou plusieurs arêtes. Une subdivision particulière est la subdivision entière (ou subdivision barycentrique) qui subdivise exactement une fois toutes les arêtes du graphe. Une telle subdivision donne toujours un graphe biparti. La subdivision entière de Kn, notée SKn, jouera un rôle important dans la structure cellulaire de la classe de graphes étudiée dans le chapitre 4. En particulier, nous pouvons observer que SK3 correspond au cycle C6 de longueur 6. Le graphe SKn a n + ¡ n 2 ¢ sommets et n(n −1) arêtes. Les n sommets de Kn sont appelés les sommets originaux de SKn et les nouveaux sommets sont appelés les sommets subdivisions
Résumé |
