• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

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

Chatelain, Vanessa 18 March 2011 (has links) (PDF)
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.

Page generated in 0.0799 seconds