Affordable Access

Cubes partiels : complétion, compression, plongement

Authors
  • Philibert, Manon
Publication Date
Dec 03, 2021
Source
HAL
Keywords
Language
French
License
Unknown
External links

Abstract

Les sous-graphes isométriques d'hypercubes (dit cubes partiels) constituent une classe centrale de la théorie métrique des graphes. Ils englobent des familles de graphes importantes (arbres, graphes médians, graphes de topes de complexes de matroïdes orientés, etc.), provenant de différents domaines de recherche, tels que la géométrie discrète, la combinatoire ou la théorie géométrique des groupes.Nous étudions tout d'abord la structure des cubes partiels de VC-dimension $2$. Nous montrons que ces graphes peuvent être obtenus par amalgamations à partir de cycles et de subdivisions entières des graphes complets.Cette décomposition nous permet d’obtenir diverses caractérisations. En particulier, tout cube partiel de VC-dimension $2$ peut être complété en cube partiel ample de VC-dimension $2$. Nous montrons ensuite que les graphes de topes des matroïdes orientés et des complexes de matroïdes orientés uniformes peuvent aussi être complétés en cubes partiels amples de même VC-dimension.En utilisant un résultat de Moran et Warmuth, nous établissons que ces classes vérifient la conjecture de Floyd et Warmuth, l'une des plus vielles conjectures en théorie de l'apprentissage. C'est-à-dire qu'elles admettent des schémas de compression (étiquetés non propres) de taille leur VC-dimension.Par la suite, nous décrivons un schéma de compression étiqueté propre de taille $d$ pour les complexes de matroïdes orientés de VC-dimension $d$, généralisant ainsi le résultat de Moran et Warmuth pour les amples. Enfin, nous fournissons une caractérisation par pc-mineurs exclus et parsous-graphes isométriques interdits des cubes partiels plongeables isométriquement dans la grille $\mathbb{Z}^2$ et dans le cylindre $P_n \square C_{2k}$ pour un certain $n$ et $k > 4$.

Report this publication

Statistics

Seen <100 times