Relation entre l'expansion du graphique et la conductance

Question

Je suis assez confus quant à la relation exacte entre l'expansion d'un graphique et sa conductance. Ma première question est:

• Quelqu'un pourrait-il me pointer vers une référence qui discute tous les deux De ces notions? (J'ai trouvé diverses notes de conférence sur des sujets connexes, mais ceux-ci semblent se concentrer sur l'expansion ou sur la conductance ...)

J'ai lu que l'expansion de $ g $ est une mesure pour la vitesse de mélange d'une marche aléatoire sur $ g $, c'est-à-dire le temps de s'approcher de la distribution stationnaire. Pour un graphique $ D $-régulier avec une expansion constante, par exemple, le temps de mélange est $ theta ( log n) $. Il en va de même pour la conductance $ phi (g) $, c'est-à-dire si $ phi (g) $ est constant, alors une marche aléatoire sur $ g $ mélangera également $ theta ( log n) $ time. De plus, cette propriété de conductance détient même dans des graphiques non réguliers et, pour des graphiques réguliers $ d $, l'expansion de $ g $ peut être trouvée en divisant simplement la conductance de $ g $ par $ d $. Cela soulève la question suivante:

• Pourquoi devrions-nous considérer l'expansion d'un graphique $ g $, alors que la conductance semble être une mesure plus forte (qui subsume l'expansion)?