Des constructions meilleures qu'une construction aléatoire.

Je m'intéresse à des exemples de constructions dans la théorie de la complexité qui sont meilleures que des constructions aléatoires.

Le seul exemple d'une telle construction que je connaisse est dans le domaine des codes correcteurs d'erreurs. Les codes à géométrie algébrique sont meilleurs dans une certaine gamme de paramètres qu'un code aléatoire.

On peut facilement construire de tels exemples artificiels. Je m'intéresse aux exemples comme les codes de géométrie algébrique, où il est facile de faire une construction aléatoire et où il n'est pas évident de faire mieux.

$\lambda_2\leq \frac{2\sqrt{D-1}}{D}$$D$$\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$$\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$$o(1)$$0$$D$$N\rightarrow \infty$

$\{ 1,\ldots,N \}$$\{ 1,\ldots,N\}$$N^{0.9}$$N^{1-o(1)}$

$n$$n-1$

En général, les constructions aléatoires et les constructions gourmandes atteignent les mêmes limites (par exemple, les codes de correction d'erreur). Une fois, j'ai entendu un discours de Lovasz où il a dit que les choix gourmands et les choix aléatoires sont essentiellement les mêmes. Donc, toute construction qui bat la construction gourmande devrait répondre à votre question. À titre d'exemple rapide, les constructions qui atteignent la capacité de Sperner des graphiques sont de ce type. Comme l'a dit Peter Shor, il y a vraiment beaucoup d'exemples en combinatoire extrême.