Domanda

Considera la famiglia dei grafici di laurea $ 6 $ con vertice set $ v_n = (a, b, c) $ per tutti $ 0 leq a, b, c leq n-1 $ con $ (a, b, c) $ collegato a $ (a-1, b, c), (a+1, b, c), (a, b-1, c), (a, b+1, c), (a, b, c- 1), (a, b, c+1) $, con tutte le operazioni modulo $ n $. Mostra che questa non è una famiglia di grafici degli espansori.

Ho lottato con questa domanda per oltre una settimana. Ho provato a guardare dalla prospettiva algebrica e mostrare che il divario spettrale sta diventando più piccolo quando N (il numero di vertici) aumenta. Ma mi sono bloccato a lungo e ora non so se sono affatto sulla buona strada.

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top