Nouvelle borne en O(log n)^{1/4} pour le problème de Komlos (suivant Bansal-Jiang, et Bansal et al.)

par Maud Szusterman

jeudi 18 déc. 2025, 15:00 → 17:00 Europe/Paris

Salle Olga Ladyjenskaïa (IHP - Bâtiment Borel)

On commencera par définir la mesure de discrépance β(U,V) entre deux corps convexes symétriques: le problème de Komlós est d'estimer β(B2,B_∞). On rappellera la méthode classique de coloriage partiel (Gluskin/Spencer/Giannopoulos) qui donne une borne en O(log n) pour ce problème. Ensuite on énoncera le théorème-5K de Banaszczyk, qui donne la borne β(B2,B_∞)≤ 7 ( log n)^{1/2}. On énoncera un théorème dû à Dadush et al. qui énonce que, pour un n-uplet donné de vecteurs de B_2, on a équivalence entre un "énoncé type 5K" et l'existence d'une certaine distribution sous-gaussienne. Dans un second temps, on présentera l'algorithme de coloriage de Gram-Schmidt (dû à Bansal et al., 2018) et on expliquera, à l’aide de la transformée de Laplace du vecteur aléatoire produit par l’algorithme, comment retrouver la borne en (log n)^{1/2} avec cette approche. On espère illustrer ce faisant, en quoi (log n)^{1/2} apparait comme une barrière pour ce type d'algorithmes. Enfin, l'exposé présentera une partie des avancées récentes de Bansal et Jiang (2025). On énoncera la conjecture de Beck-Fiala (qu'on peut voir comme un cas particulier de Komlós), que ces auteurs ont presque entièrement résolue. Nous détaillerons ensuite par quelles techniques ils ont réussi à transférer leur (nouvelle) borne pour Beck-Fiala en une borne inédite de \tilde{O}(log n)^{1/4} pour le problème de Komlós