Comment construire pratiquement des graphiques d'extensions réguliers?

J'ai besoin de construire un graphique d'expansion d-régulier pour quelques petits d fixes (comme 3 ou 4) de n sommets.

Quelle est la méthode la plus simple pour le faire dans la pratique? Construire un graphique aléatoire régulier, qui s'est avéré être un expandeur?

J'ai également lu sur les constructions Margulis et les graphiques Ramanujan qui sont des expanseurs et une construction utilisant un produit en zig-zag. Wikipedia donne un aperçu agréable mais très court: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Mais quelle méthode dois-je choisir dans la pratique?

Pour moi, ces méthodes semblent toutes très compliquées à mettre en œuvre et en particulier à comprendre et peut-être assez spécifiques. N'y a-t-il pas des méthodes plus faciles, peut-être basées sur des permutations ou ainsi, pour générer pratiquement une séquence de graphiques d'expansion d-regular?

Est-il peut-être plus facile de construire des graphes expanseurs bipartis d-regular?

J'ai aussi une autre question: qu'en est-il des familles de mauvais expandeurs d-regular? Une telle notion a-t-elle un sens? Peut-on construire une famille de graphes d-réguliers (qui sont bien sûr connectés) aussi mauvais que possible au sens d'un expandeur?

Merci d'avance.

graph-theory combinatorics cryptography discrete-mathematics expanders user2145167
la source

Il existe des constructions explicites plus faciles que celles que vous avez énumérées, mais les graphiques aléatoires devraient faire l'affaire et avoir de meilleurs paramètres.

Yuval Filmus

Pouvez-vous peut-être donner des noms ou des références des constructions? Par de meilleurs paramètres, vous voulez dire une meilleure expansion (de bord), je suppose?

user2145167

András a donné l'exemple que j'avais en tête, mais en général, les graphiques aléatoires sont (presque toujours) meilleurs que les constructions explicites. Non seulement l'expansion des bords est plus grande, mais toute autre propriété similaire utile à votre algorithme est probablement automatiquement satisfaite par des graphiques aléatoires.

Yuval Filmus

Ok, pour le degré 3, l'exemple d'András ou les graphiques aléatoires semblent être assez bons pour mon application. Il serait intéressant, notamment en ce qui concerne les graphes aléatoires, de construire une famille de graphes à 3 reg qui ne soit pas un expandeur. Mais c'est probablement très difficile ou pas possible?

user2145167

Prenez une union de

s. Si vous voulez un graphe connecté, supprimez un bord de chaque

(formant un graphe connu sous le nom de graphe en losange) et connectez-les dans un cycle.

K_{4}

$K_4$

K_{4}

$K_4$

Yuval Filmus

Réponses:

Si cela ne vous dérange pas les graphiques avec auto-boucles, la famille d'extensions "la plus simple" est probablement celle-ci, donnant des expandeurs qui sont 3-réguliers.

Commencez par un nombre premier et construisez des sommets numérotés de à . Pour chaque sommet , connectez à et , modulo . Connectez également au sommet unique tel que $p$ $0$ $p-1$ $u \ne 0$ $u$ $u-1$ $u+1$ $p$ $u$ $v$ . $uv \equiv 1 \mod p$

$6$ $0$ $1$ $3$ $5$ $2$ $4$

Voir /mathpro/124708/an-expander-graph pour plus de discussion et références. Il existe de nombreux pointeurs plus détaillés en recherchant «expander» dans CSTheory , Math.SE et MO .

Comme Yuval Filmus le fait remarquer, la construction aléatoire est susceptible de donner de meilleurs résultats en général, mais bien sûr, elle ne peut pas produire un expandeur (en particulier pour les petits graphiques).

András Salamon
la source

Merci pour la remarque. J'avais déjà cherché des expandeurs sur les autres sites mais pas sur MO, il semble vraiment y avoir plus de résultats.

user2145167

Étant donné qu'un graphique régulier aléatoire est un expanseur whp (suivez la référence donnée dans la documentation du code MATLAB lié ci-dessous), j'ai utilisé une fois ce qui suit:

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m

Hoda
la source