Relazione tra espansione del grafico e conduttanza

Question

Sono abbastanza confuso sull'esatta relazione tra l'espansione di un grafico e la sua conduttanza. La mia prima domanda è:

• Qualcuno potrebbe indicarmi un riferimento che discute Entrambi di queste nozioni? (Ho trovato vari appunti di lezione sugli argomenti correlati, ma questi sembrano concentrarsi sull'espansione o sulla conduttanza ...)

Ho letto che l'espansione di $ g $ è una misura per la velocità di miscelazione di una passeggiata casuale su $ g $, cioè il tempo per avvicinarsi alla distribuzione stazionaria. Per un grafico regolare $ d $ con espansione costante, ad esempio, il tempo di miscelazione è $ theta ( log n) $. Lo stesso sembra essere vero per la conduttanza $ phi (g) $, cioè, se $ phi (g) $ è costante, allora una passeggiata casuale su $ g $ mescolerà anche $ theta ( log n) $ tempo. Inoltre, questa proprietà della conduttanza detiene anche in grafici non regolari e, per $ d $ -Regolari grafici, l'espansione di $ g $ può essere trovata semplicemente dividendo la conduttanza di $ g $ di $ d $. Questo pone la seguente domanda:

• Perché dovremmo prendere in considerazione l'espansione di un grafico $ g $, quando la conduttanza sembra essere una misura più forte (che somma l'espansione)?