Return to search

Contributions à la théorie des matroïdes : polytope des bases, orientations et algorithmes

Dans cette thèse on étudie différents problèmes portant sur les matroïdes et les matroïdes orientés. On s'intéresse à trois sujets particuliers : la décomposition du polytope des bases d'un matroïde, l'orientation de matroïdes et le jeu de commutation de Shannon. Plus précisément dans le chapitre 2 nous étudions une décomposition spéciale introduite par Lafforgue. Pour un matroïde M, une décomposition du polytope des bases d'un matroïde P(M) est une décomposition de la forme P(M) = St i=1 P(Mi) où chaque P(Mi) est également un polytope des bases d'un matroïde pour un certain matroïde Mi, et pour chaque 1 i 6= j t, l'intersection P(Mi) \ P(Mj) est une face de P(Mi) et de P(Mj). Dans cette thèse, nous étudions la séparation par hyperplan, autrement dit la décomposition du polytope quand t = 2. Nous donnons des conditions suffisantes sur M pour que P(M) puisse avoir une séparation par hyperplan. Nous caractérisons également les cas où P(M1 M2) a une séparation par hyperplan où M1 M2 dénote la somme directe des matroïdes M1 et M2. Nous montrons finalement que P(M) n'a pas de séparation par hyperplan si M est binaire. Dans le chapitre 3 nous étudions la classe des matroïdes orientés du réseau. Après avoir donné une caractérisation complète des matroïdes orientés du réseau en fonction de l'union de matroïdes orientés uniformes de rang un, nous montrons que cette classe est fermée par dualité et par mineurs. Nous étudions ensuite les simplexes de l'arrangement d'hyperplans découlant de matroïdes orientés du réseau. Nous présentons une caractérisation de ces simplexes et construisons un arrangement de n hyperplans en dimension d contenant O(2k(n k )k) simplexes avec n < k = bd 2 c. Nous approfondissons une question posée par Grünbaum [Grünbaum, 1971] concernant les colorations des arrangements de pseudodroites. Nous prolongeons la question de Grünbaum à des arrangements d'hyperplans et répondons par l'affirmative à cette question généralisée pour les arrangements découlants de matroïdes orientés du réseau. Dans le chapitre 4 nous nous sommes intéressés à une une version sur les matroïdes orientés du célèbre jeu de commutation de Shannon, version introduite par Y.O. Hamidoune et M.Las Vergnas[Hamidoune et Las Vergnas, 1997a] en 1986. Ils ont conjecturé que la classification du jeu de commutation sur les matroïdes orientés est identique à la classification de la version non orientée. Dans cette thèse, nous confortons cette conjecture en montrant sa validité pour la classe infinie de matroïdes orientés obtenues comme union de matroïdes orientés uniformes de rang 1 et/ou de rang 2.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00824903
Date18 March 2011
CreatorsChatelain, Vanessa
PublisherUniversité Pierre et Marie Curie - Paris VI
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.002 seconds