Zig and Zag en streaming ou téléchargement

Produit zig-zag de graphes

En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes G {\displaystyle G} et H {\displaystyle H} , noté G ∘ H {\displaystyle G\circ H} , prend en arguments un grand graphe G {\displaystyle G} et un petit graphe H {\displaystyle H} et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si H {\displaystyle H} est un bon graphe expanseur, alors le taux d'expansion du graphe résultat G ∘ H {\displaystyle G\circ H} est seulement un peu moins bon que le taux d'expansion de G {\displaystyle G} . De manière informelle, le produit zig-zag G ∘ H {\displaystyle G\circ H} remplace chaque sommet de G {\displaystyle G} par une copie de H {\displaystyle H} (un « nuage », cloud en anglais) et relie les sommets en trois étapes : une première (le zig) à l'intérieur du nuage, suivi d'une deuxième entre deux nuages, et enfin une troisième (le zag) à l'intérieur du nuage d'arrivée. Le produit zig-zag a été introduit par Omer Reingold, Salil Vadhan et Avi Wigderson en 2002 et a été utilisé pour la construction explicite d'expanseurs et d'extracteurs de degré constant. Les auteurs ont obtenu le prix Gödel pour ce travail. Ultérieurement le produit zig-zag a été employé en théorie de complexité pour prouver que les classes de complexité SL (espace logarithmique symétrique) et L (espace logarithmique) coïncident.