Conductance et diamètre dans les graphiques réguliers

Étant donné un graphe régulier non orienté , quelle est la relation entre son diamètre - défini comme la plus grande distance entre deux nœuds - et sa conductance, définie comme où est le nombre d'arêtes se croisant entre et . $G=(V,E)$

min_{S \subset V} \frac{e (S, S^{c})}{min (| S |, | S^{c} |)},

$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$

e (S, S^{c})

$e(S,S^c)$

S

$S$

S^{c}

$S^c$

Plus concrètement , je suppose que sais le diamètre est au moins (ou plus) $D$ . Qu'est-ce que cela me dit sur la conductance, le cas échéant? Et, inversement, supposons que je sais que la conductance est au plus (ou au moins) $\alpha$ . Qu'est-ce que cela me dit sur le diamètre, le cas échéant?

graph-theory co.combinatorics expanders robinson
la source

Il semble que la propriété que vous demandez est l' expansion du graphique au lieu de la conductance du graphique, qui est définie comme , où est défini comme . Laquelle est la propriété que vous souhaitez ??

min_{S \subseteq V} e (S, \bar{S}) / min {v o l (S), v o l (\bar{S})}

$\min_{S \subseteq V} \ {e(S,\overline{S})}/{\min\{\mathsf{vol}(S), \mathsf{vol}(\overline{S})\}}$

v o l (S)

$\mathsf{vol}(S)$

\sum_{v \in S} \deg (v)

$\sum_{v \in S} \deg(v)$

Hsien-Chih Chang 張顯之

@ Hsien-Chi Chang - puisque le graphique est régulier, je pense que la conductance et l'expansion devraient être les mêmes jusqu'à un facteur multiplicatif du degré .

d

$d$

robinson

Ah, je n'ai pas remarqué que le graphique est régulier. Merci pour l'explication.

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之: Je pensais que l'expansion du graphe et la conductance du graphe étaient le même concept. Avez-vous des références sur la définition dans votre commentaire?

Tim

Comme le note Hsieh, votre définition de la conductance est différente de celle que je connais par un facteur de , où est le degré du graphique régulier. Ceci est également connu comme l'expansion des bords pour les graphiques réguliers. $d$ $d$

Une relation entre l'expansion des bords et le diamètre est assez facile à montrer. Intuitivement, un expandeur est "comme" un graphe complet, donc tous les sommets sont "proches" les uns des autres. Plus formellement, laissez

min_{S \subseteq V} \frac{e (S, S^{c})}{ré \cdot min {| S |, | S^{c} |}} \geq α

$\min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha$

Prenez n'importe quel ensemble de sommets avec . Il y a au moins arêtes sortant de et puisque est -régulier, le voisinage de (y compris lui-même) est de taille au moins . Appliquer cette revendication de manière inductive, à partir de pour tout sommet $S$ $|S| \leq |V|/2$ $\alpha d |S|$ $S$ $G$ $d$ $S$ $S$ $(1+\alpha)|S|$ $S = \{u\}$ $u$ , Nous voyons que pour certains , « s -Hop quartier a une taille au moins . Par conséquent, le voisinage -hop de tout sommet doit intersecter le voisinage -hop de , sinon le graphique aurait plus de sommets, une contradiction. Vous avez donc $t = O(\log_{1 + \alpha } |V|)$ $u$ $t$ $|V|/2$ $t+1$ $v$ $t$ $u$ $|V|$

ré = O (\frac{Journal | V |}{Journal (1 + α)})

$D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right)$

Bien entendu, il s'ensuit également que le fait d'avoir une borne inférieure sur le diamètre implique une borne supérieure sur l'expansion du bord.

Je ne pense pas qu'un petit diamètre implique une conductance. Si vous n'insistez pas sur des graphiques réguliers (et utilisez la définition de Hsieh), deux graphiques complets connectés par un seul bord fournissent un contre-exemple.

Sasho Nikolov
la source

Je suis sur le point de poster une réponse et maintenant je n'ai plus à le faire, je peux simplement voter pour la vôtre à la place;) Merci pour la bonne réponse!

Hsien-Chih Chang 張顯之

J'espère que le temps total que vous et moi avons passé en dehors de la recherche a été minimisé :)

Sasho Nikolov

@robinson: ce simple fait et ce mélange rapide sont à la base de nombreuses (la plupart?) applications des familles d'extensions de graphes réguliers. la propriété de petit diamètre, par exemple, est la base de l'application pour résoudre la connectivité st dans logspace

Sasho Nikolov

ma réponse d'origine avait un bug: l'argument que j'avais écrit était pour l'expansion des sommets, mais nous travaillons ici avec l'expansion des bords. j'ai corrigé le bug, et la limite est maintenant légèrement pire

Sasho Nikolov

Conductance et diamètre dans les graphiques réguliers

Réponses: