Contributions in the matroid theory : base polytope, orientations, algorithms

In chapter 2, we study a special decomposition intoduced by Lafforgue. More precisely, let P(M) be the matroid base polytope of a matroid M. A matroid base polytope decomposition of P(M) is a decomposition of the form P(M) = St i=1 P(Mi) where each P(Mi) is also a matroid base polytope for some matroid Mi, and for each 1 i 6= j t, the intersection P(Mi)\P(Mj) is a face of both P(Mi) and P(Mj). In this thesis, we investigate hyperplane splits, that is, polytope decompositions when t = 2. We give sufficient conditions for M so P(M) has a hyperplane split and characterize when P(M1 M2) has a hyperplane split where M1 M2 denote the direct sum of matroids M1 and M2. We also prove that P(M) has not a hyperplane split if M is binary. Finally, we show that P(M) has not a decomposition if its 1-skeleton is the hypercube. In chapitre 3 we investigate the class of lattice oriented matroids. After giving a complete characterization of lattice oriented matroids in terms of union of rank-1 uniform oriented matroids, we show that this class is closed under duality and minors. We then study the simplexes of the hyperplane arrangements arising from lattice oriented matroids. We present a characterization of these simplexes and contruct arrangements of n hyperplanes in dimension d containing O(2k(n k )k) simplexes with n < k = bd 2 c. We finally investigate a question by Grünbaum [Grünbaum, 1971] concerning colorings of pseudoline arrangements. We extend Grünbaum's question to arrangements of hyperplanes and answer affirmatively the generalized question for arrangements arising from lattice oriented matroids. In chapitre 4 we are interested in an oriented matroid version of the well-known Shannon's switching game introduced by Hamidoune and Las Vergnas[Hamidoune et Las Vergnas, 1997a] in 1986. They conjectured that the classification of the directed switching game on an oriented matroids is identical to the classification of non-oriented version. In this thesis, we support this conjecture by showing its validity for an infinity class of oriented matroids obtained as unions of rank-1 and/or rank-2 uniform oriented matroids.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00824903
Author Chatelain, Vanessa
Maintainer CCSD
Last Updated May 11, 2026, 01:31 (UTC)
Created May 11, 2026, 01:31 (UTC)
Identifier NNT: 2011PA066253
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Equipe combinatoire et optimisation (C&O) ; Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)) ; Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
creator Chatelain, Vanessa
date 2011-03-18T00:00:00
harvest_object_id 9cd3fd5e-f6e4-4560-ac0f-06a59840ba3b
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-03-01T00:00:00
set_spec type:THESE