Soutenance mémoire
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 [93] 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² 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 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² 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(n2 ) 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 Rd et évitant les autres. LAWRENCE les appelle 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].
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.
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
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.
|
Table des matières
Introduction
1 Rappels de théorie des graphes et de combinatoire
1.1 Notions de base de théorie des graphes
1.1.1 Graphes usuels
1.1.2 Opérations sur les graphes
1.1.3 Notions de théorie métrique des graphes
1.2 Notions d’apprentissage automatique
1.2.1 Classes de concepts et graphe de 1-inclusion
1.2.2 Modèle d’apprentissage PAC et VC-dimension
1.2.3 Lemme de Sauer et lemme du Sandwich
1.2.4 Schéma de compression
1.3 Notions de théorie des complexes de matroïdes orientés
1.3.1 Matroïdes orientés
1.3.2 Complexes de matroïdes orientés
1.3.3 Systèmes amples
2 Cubes partiels : rappels
2.1 La relation d’équivalence Θ
2.1.1 PC-mineurs
2.1.2 Expansions isométriques
2.2 Graphes médians
2.3 Cubes partiels amples
2.4 Graphes de topes des OMs et des COMs
2.5 État de l’art
3 VC-dimension des cubes partiels
3.1 Résultats
3.2 Pulvérisation et fibres dans les cubes partiels
3.3 Cubes partiels de VC-dimension bornée
3.4 VC-dimension et rang dans les OMs et les COMs
4 Cubes partiels bidimensionnels
4.1 Résultats
4.2 Hyperplans
4.3 Enveloppes portées des cycles de longueur 6
4.3.1 Subdivision entière de Kn
4.3.2 Les subdivisions entières de Kn sont portées
4.3.3 Enveloppes portées des cycles de longueur 6
4.4 Enveloppes convexes et portées des cycles isométriques longs
4.4.1 Enveloppes convexes des cycles isométriques longs
4.4.2 Enveloppes portées des cycles isométriques longs
4.5 Complétion en cubes partiels amples
4.5.1 Complétion canonique en graphes de topes de COMs bidimensionnels
4.5.2 Complétion en cubes partiels amples bidimensionnels
4.6 Cellules et carrières
Conclusion
