Evènement pour le groupe GT Graphes et Applications


Date 2015-12-04  14:00-15:00
TitreOn dense codes 
RésuméWe consider the sphere packing problem in arbitrary dimension: what is the maximum fraction d_n of the Euclidean space Rn that can be covered by unit balls with pairwise disjoint interiors? d_n is known for only for some small values of n, and when n grows, we only have lower bounds. A trivial lower bound states that for every n, d_n >= 2^-n. Minkowski and Hlwaka's Theorem (1905) improved this lower bound by a factor 2. Asymptotic improvements of this bound were obtained (from Rogers, 1947 up to Ball, 1992), all of them being of the form d_n >= c n 2^-n where c is a constant. This problem has a natural reformulation in graph theoretic terms as follows: let G denote the graph whose vertices are the points of the Euclidean space and edges are pair of vertices at distance at most 2 one from the other. The independent sets of G are the sphere packings: so, finding a maximum-density sphere packing is the same as finding a maximum-density independent set in this infinite graph. By using graph theoretic arguments only, Krivelevich et al. established that d_n >= 0.01 n 2^-n for sufficiently large n (2004). In a recent breakthrough, Venkatesh introduced the first superlinear improvement: there are infinitely many n such that d_n >= c n log log n 2^-n, where c is a constant. Venkatesh's result is however non-constructive. In this talk, we focus on Bachoc and Moustrou's constructive proof of Venkatesh's lower bound.  
LieuSalle 178 
OrateurArnaud Pêcher 



Aucun document lié à cet événement.

Retour
Retour à l'index