AnnalesÉcoles d'ingénieurs

Mines-Ponts PSI 2018 — Maths 1

Théorème de Komlós · 7 pages

PDF hébergé hors du site officiel — source : archive officielle (ZIP)

Le sujet démontre que la probabilité qu'une matrice aléatoire $n \times n$ à coefficients $\pm 1$ indépendants et équiprobables soit singulière tend vers $0$ . Après des estimations sur le coefficient binomial central (via la formule de Stirling) et le cas $n = 2$ , il majore la probabilité qu'une ligne tombe dans l'espace engendré par les précédentes (au plus $2^{j-n}$ ), démontre le lemme de Sperner sur les anti-chaînes et en déduit l'inégalité d'Erdős-Littlewood-Offord ; une notion d'ensemble $k$ -universel permet de traiter les dernières lignes et de conclure au théorème de Komlós.

Le sujet, partie par partie

Notations et A — Coefficients binomiaux p. 2–3

Coefficients binomiaux · Formule de Stirling · Équivalents et comparaison · Espaces vectoriels et dimension — coefficient binomial central, formule de Stirling, monotonie des coefficients binomiaux, espace de Rademacher, famille génératrice

B — Dimension 2 p. 4

Matrices et graphes aléatoires · Espérance, variance, moments · Déterminants · Espaces probabilisés — matrice aléatoire de signes, déterminant, espérance, variance, probabilité uniforme

C — Quelques bornes p. 4–5

Matrices et graphes aléatoires · Espaces vectoriels et dimension · Probabilités totales et formule de Bayes · Conditionnement et indépendance · Dualité · Espaces préhilbertiens et euclidiens — famille liée, orthogonal d'un sous-espace, pivot de Gauss, formule des probabilités totales, vecteur à coordonnées entières, indépendance des lignes

D — Théorème de Erdös-Littlewood-Offord p. 5–6

Dénombrement et combinatoire · Coefficients binomiaux · Espaces probabilisés · Groupe symétrique — anti-chaîne, lemme de Sperner, inégalité LYM, théorème d'Erdős-Littlewood-Offord, permutations, parties de cardinal $k$

E — Universalité p. 6–7

Matrices et graphes aléatoires · Espaces probabilisés · Coefficients binomiaux · Conditionnement et indépendance — ensemble $k$ -universel, réunion d'événements, sous-additivité, majoration de probabilité, indépendance

F — Théorème de Komlós p. 7

Matrices et graphes aléatoires · Espaces probabilisés · Suites numériques — théorème de Komlós, matrice aléatoire inversible, déterminant nul, limite de probabilités