Amplitude des graphes cubiques aléatoires

Considérons un graphe cubique aléatoire connecté desommets, tirés de -reg (tel que défini ici , c'est-à-dire que est pair et que deux graphiques quelconques ont la même probabilité). $G=(V,E)$ $n =|V|$ $G(n, 3$ $)$ $3n$

Bien sûr , il y a $n$ possibles recherches, largeur d ' abord un pour chaque noeud de départ $s \in V$ . Une largeur First Search $B_G$ départ au noeud $s \in V$ attribue un niveau $d(s, v)$ à chaque noeud $v \in V$ , où $d(s, v)$ est la distance entre $s$ et $v$ dans $G$ .

Disons qu'une telle recherche en $B_G$ affecte également un niveau

L (s, {u, v}) = max {d (s, u), d (s, v)}

$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$ à chaque arête

e = {u, v} \in E

$e=\{u,v\} \in E$ .

Étant donné une recherche de premier $B_G$ , soit $\alpha(B_G,i)$ le nombre d'arêtes qui ont été affectées au niveau $i$ , et soit $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ . En d'autres termes, $\alpha(B_G)$ est le nombre d'arêtes du niveau contenant plus d'arêtes que tout autre niveau. Enfin, laissez $\alpha(G)$ le maximum $\alpha(B_G)$ pour l' une des $n$ Largeur Premières recherches de $G$ .

Appelons $\alpha(G)$ l' amplitude de $G$ .

Question

Comment la valeur attendue de $\alpha(G)$ croît-elle lorsque $n$ tend vers l'infini? Rappelons que $G$ est un cube aléatoire . Plus précisément, ce que j'aimerais vraiment savoir, c'est si la valeur attendue de $\alpha(G)$ appartient à $o(n)$ .

Puisque $n$ est pair, la limite est considérée de sorte que je ne me soucie pas des impairs $n$ .

graph-theory co.combinatorics Giorgio Camerani
la source

(1) Veuillez préciser à partir de quelle distribution de probabilité vous tracez votre graphique cubique. (2) Êtes-vous intéressé par l'attente de en fonction de , ou autre chose? (3) Je suppose que est pair (sinon un graphe cubique n'existe pas). Donc, je suppose que la limite est considérée pour que vous ne vous souciez pas des impairs .

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto

@YoshioOkamoto: (1) À partir de -reg tel que défini dans stanford.edu/class/msande337/notes/… ( est pair et deux graphiques quelconques ont la même probabilité). (2) J'ai enrichi la question pour clarifier ce point. (3) Oui, est pair et la limite est considérée pour que je ne me soucie pas des impairs .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani

@SureshVenkat: Merci d'avoir amélioré la lisibilité de la question ;-)

Giorgio Camerani

Permettez-moi de dire qu'il est fort probable qu'il y ait des résultats de concentration pour sur des graphiques cubiques aléatoires, ce qui signifie que la valeur attendue, la valeur de probabilité élevée, etc., sont toutes les mêmes. À moins que le PO ne précise, je pense qu'une réponse à l'une de ces questions serait une réponse raisonnable à cette question.

α (G)

$\alpha(G)$

Peter Shor

@WalterBishop: Permettez-moi de poser une autre question. Comment définissez-vous si est déconnecté?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Réponses:

L'amplitude pour les graphes expanseurs. Un graphe aléatoire aléatoire à 3 intervalles est asymptotiquement presque sûrement un graphe d'expansion (voir Wikipedia) , donc l'espérance de l'amplitude sera , car la probabilité qu'il ne s'agisse pas d'un graphe d'expansion passe à car va à . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Pour un graphe d'extension avec le paramètre , pour tout ensemble de sommets avec , il y a voisins de l'ensemble. Maintenant, laissez le nombre de sommets au niveau être , avec . Nous avons alors de la propriété d'expansion que tant que n'est pas trop grand (c'est-à-dire que nous n'avons pas encore inclus la moitié des sommets) Maintenant, recherchez le niveau qui contient le sommet . Autrement dit, donc et $\beta$ $s$ $s \leq n/2$ $\beta s$ $j$ $\ell_j$ $\ell_0=1$ $j$

ℓ_{j} \geq β \sum_{i = 0}^{j - 1} ℓ_{i}

$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$

ℓ_{j}

$\ell_j$

\frac{n}{3}

$\frac{n}{3}$

\sum_{i = 0}^{j - 1} ℓ_{i} < n / 3

$\sum_{i=0}^{j-1} \ell_i < n/3$

\sum_{i = 0}^{j} ℓ_{i} \geq n / 3

$\sum_{i=0}^{j} \ell_i \geq n/3$ . Si ce niveau est grand, c'est-à-dire , nous avons terminé. Sinon, le niveau suivant a la taille et nous avons fini.

ℓ_{j} \geq n / 6

$\ell_j \geq n/6$

ℓ_{j + 1} \geq β \sum_{i = 0}^{j} ℓ_{i} \geq β \frac{n}{3},

$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$

Bien que cette preuve examine le nombre de sommets d'un niveau plutôt que le nombre d'arêtes (ce que l'OP a demandé), il y a toujours au moins autant d'arêtes ajoutées à l'étape que de sommets au niveau , car chaque sommet doit être atteint par un bord. $i$ $i$

Peter Shor
la source

Merci pour votre réponse! C'est très surprenant (du moins pour moi): même si le nombre total d'arêtes est , et le nombre de niveaux est , le plus le niveau bondé a toujours des bords . Ainsi, les bords ne sont pas répartis uniformément entre les niveaux: mon intuition (empirique, erronée) était que, à part quelques niveaux initiaux et quelques niveaux finaux, il aurait dû y avoir des niveaux centraux parmi lesquels les bords ont été dispersés quelque peu uniformément.

m = 1.5 \cdot n \in Θ (n)

$m = 1.5 \cdot n \in \Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Giorgio Camerani

avec «empirique», vous voulez dire que vous avez réellement effectué des tests? est d'environ pour les graphes aléatoires cubiques, voir ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

didest

Oui, j'ai exécuté des tests de à et mesuré la quantité . Si approchait de lorsque augmentait, cela aurait donné des preuves empiriques que . Autour de , était d'environ , tandis que vers , était d'environ (bien sûr, je n'ai jamais considéré ces chiffres comme des preuves empiriques, car est encore trop petit pour représenter une asymptotique). Mais quand j'ai dit "intuition empirique"

n = 100

$n = 100$

n = 150000

$n = 150000$

k = \frac{α (G)}{m}

$k = \frac{\alpha(G)}{m}$

k

$k$

0

$0$

n

$n$

α (G) \in o (n)

$\alpha(G) \in o(n)$

n = 100

$n=100$

k

$k$

0.3

$0.3$

n = 150000

$n=150000$

k

$k$

0.26

$0.26$

n = 150000

$n = 150000$

Giorgio Camerani

... Je voulais dire un vrai (mauvais) sentiment plutôt que le résultat des tests: je sentais quelque peu que ces BFS devaient avoir une forme de "saucisse" (c'est-à-dire minuscules aux extrémités, et de constance constante au milieu). "Ils doivent être comme ça", ai-je pensé. La preuve ci-dessus montre à quel point mon intuition était fausse. Néanmoins, je suis toujours surpris: bords, niveaux, mais pas bords à chaque niveau.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

O (\frac{n}{l o g (n)})

$O(\frac{n}{log(n)})$

Giorgio Camerani

La réponse de Peter Shor est vraiment bonne, mais il y a une autre façon de répondre à cela: prouver que la largeur de l'arbre est supérieure de deux fois l'amplitude (la version vertex). Puisque nous savons que les expandeurs 3-réguliers ont une largeur d'arbre linéaire, nous avons terminé.

Voir la construction d'une décomposition d'arbre à partir d'un arbre BFS, c'est la diapositive 15 de cette présentation: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Il est facile de voir que la taille de chaque sac est délimitée par deux fois le niveau le plus large.

didest
la source

Merci pour votre réponse, cette présentation a été très utile.

Giorgio Camerani