Show simple item record

dc.contributor.advisorChristine Bachoc
dc.contributor.advisorArnaud Pêcher
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorMOUSTROU, Philippe
dc.contributor.otherKarim Belabas [Président]
dc.contributor.otherDamien Stehlé [Rapporteur]
dc.contributor.otherFrank Vallentin [Rapporteur]
dc.contributor.otherSinai Robins
dc.date.accessioned2024-04-04T03:06:58Z
dc.date.available2024-04-04T03:06:58Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193389
dc.identifier.nnt2017BORD0802
dc.description.abstractUn graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets.
dc.description.abstractEnA distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs.
dc.language.isoen
dc.subjectGraphes métriques
dc.subjectRéseaux Euclidiens
dc.subjectEmpilement de sphères
dc.subjectBorne de Minkowski-Hlawka
dc.subjectCodes linéaires
dc.subjectPolytopes pavant l’espace par translation
dc.subjectNombre chromatique
dc.subject.enDistance graphs
dc.subject.enEuclidean lattices
dc.subject.enSphere packing
dc.subject.enMinkowski- Hlawka bound
dc.subject.enLinear codes
dc.subject.enParallelohedra
dc.subject.enChromatic number
dc.titleGraphes métriques géométriques, réseaux et polytopes
dc.title.enGeometric distance graphs, lattices and polytopes
dc.typeThèses de doctorat
dc.subject.halMathématiques [math]/Mathématiques générales [math.GM]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionUniversité de Bordeaux
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde ; 1991-....)
hal.identifiertel-01677284
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//tel-01677284v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Graphes%20m%C3%A9triques%20g%C3%A9om%C3%A9triques,%20r%C3%A9seaux%20et%20polytopes&rft.atitle=Graphes%20m%C3%A9triques%20g%C3%A9om%C3%A9triques,%20r%C3%A9seaux%20et%20polytopes&rft.au=MOUSTROU,%20Philippe&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record