Ho bisogno di costruire un grafo di espansione d-regolare per qualche piccolo d fisso (come 3 o 4) di n vertici.
Cosa è il metodo più semplice per farlo in pratica? Costruire un grafo d-regolare casuale, che ha dimostrato di essere a.a.s. un espansore?
Ho anche letto di costruzioni Margulis e grafici Ramanujan che sono espansori e di una costruzione che utilizza un prodotto a zig-zag. Wikipedia offre una panoramica carina ma molto breve: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Ma quale metodo scelgo in pratica?
Per me, questi metodi sembrano tutti molto complicati da implementare e in particolare da capire e forse abbastanza specifici. Non esistono metodi più semplici, forse basati su permutazioni o giù di lì, per generare praticamente una sequenza di grafi espansori d-regolari?
È forse più facile costruire grafi espansori bipartiti d-regolari?
Ho anche unaltra domanda: che dire delle famiglie di pessimi espansori d-regolari? Questa nozione ha senso? Si può costruire una famiglia di grafi d-regolari (che sono ovviamente connessi) che sia il più pessima possibile in il senso di un espansore?
Grazie in anticipo.
Commenti
- Ci sono costruzioni esplicite più semplici di quelle che hai elencato , ma i grafici casuali dovrebbero fare il trucco e avere parametri migliori.
- Puoi forse dare nomi o riferimenti alle costruzioni? Per parametri migliori, intendi una migliore espansione (bordo), immagino?
- Andr á s ha fornito lesempio che avevo in mente, ma in generale i grafici casuali sono (quasi sempre) migliori delle costruzioni esplicite. Non solo lespansione del bordo è maggiore, un y unaltra proprietà simile che è utile per il tuo algoritmo è probabilmente soddisfatta automaticamente da grafici casuali.
- Ok, per il grado 3, lesempio di Andr á o i grafici casuali sembra essere abbastanza buono per la mia applicazione. Sarebbe interessante, in particolare per quanto riguarda i grafi casuali, costruire una famiglia di grafi 3-reg che non sia un expander. Ma questo è probabilmente molto difficile o impossibile?
- Prendi ununione di $ K_4 $ s. Se desideri un grafico connesso, rimuovi un bordo da ogni $ K_4 $ (formando un grafico noto come grafico a rombi) e collegali in un ciclo.
Risposta
Se non ti interessano i grafici con i loop automatici, la famiglia di espansori “più semplice” è probabilmente questa, che fornisce espansori 3-regolari.
Inizia con un numero primo $ p $ e costruisci vertici numerati da $ 0 $ a $ p-1 $. Per ogni vertice $ u \ ne 0 $, collega $ u $ a $ u-1 $ e $ u + 1 $ , modulo $ p $. Collega anche $ u $ al vertice univoco $ v $ in modo tale che $ uv \ equiv 1 \ mod p $.
Come esempio, il grafico a 7 vertici nella famiglia è un ciclo di 7 con vertici numerati in sequenza attorno al ciclo; ci sono cicli automatici su $ 6 $, $ 0 $ e $ 1 $; infine, ci sono accordi che si uniscono a $ 3 $ e $ 5 $ e $ 2 $ e $ 4 $.
Vedere https://mathoverflow.net/questions/124708/an-expander-graph per ulteriori discussioni e riferimenti. Ci sono molti suggerimenti più dettagliati cercando su ” expander “in CSTh eory , Math.SE e MO .
Come sottolinea Yuval Filmus, è probabile che la costruzione casuale dia risultati migliori in generale, ma ovviamente potrebbe non produrre un espansore (specialmente per i piccoli grafici).
Commenti
- Grazie per il commento. Avevo già cercato espansori su altri siti ma non su MO, sembra che ci siano davvero più risultati.
Risposta
Dato un grafo regolare casuale è un espansore whp (segui il riferimento fornito nella documentazione del codice MATLAB linkato di seguito), una volta ho usato quanto segue: