Amplitude de gráficos cúbicos aleatórios

Considere um gráfico cúbico aleatório conectado devértices, extraídos de reg (como definido aqui , ou seja, é par e quaisquer dois gráficos têm a mesma probabilidade). $G=(V,E)$ $n =|V|$ $G(n, 3$ $)$ $3n$

Claro que existem possíveis Pesquisas largura Em primeiro lugar, uma para cada nó de partida . Uma largura Primeira pesquisa começando pelo nó atribui um nível a cada nó , em que é a distância entre e em . $n$ $s \in V$ $B_G$ $s \in V$ $d(s, v)$ $v \in V$ $d(s, v)$ $s$ $v$ $G$

Digamos que essa pesquisa de largura da primeira pesquisa também atribua um nível a cada extremidade . $B_G$

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

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

e = {u, v} \in E

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

Dada uma Largura da Primeira Pesquisa $B_G$ , seja $\alpha(B_G,i)$ o número de arestas ao qual foi atribuído o nível $i$ , e $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ . Em outras palavras, $\alpha(B_G)$ é o número de arestas do nível que contém mais arestas do que qualquer outro nível. Finalmente, deixou $\alpha(G)$ ser o máximo $\alpha(B_G)$ para qualquer um dos $n$ largura Primeira Pesquisas de $G$ .

Vamos chamar $\alpha(G)$ a amplitude do $G$ .

Questão

Como o valor esperado de $\alpha(G)$ cresce à medida que $n$ tende ao infinito? Lembre-se de que $G$ é cúbico aleatório . Mais precisamente, o que eu realmente gostaria de saber é se o valor esperado de $\alpha(G)$ pertence a $o(n)$ .

Como $n$ é par, o limite é considerado para que eu não me importe com ímpares $n$ .

graph-theory co.combinatorics Giorgio Camerani
fonte

(1) Especifique a partir de qual distribuição de probabilidade você desenha seu gráfico cúbico. (2) Você está interessado na expectativa de em função de ou de alguma outra coisa? (3) Suponho que seja par (caso contrário, não existe um gráfico cúbico). Então, acho que o limite é considerado de modo que você não se importa com estranho é.

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto

@YoshioOkamoto: (1) De reg conforme definido em stanford.edu/class/msande337/notes/… ( é par e quaisquer dois gráficos têm a mesma probabilidade). (2) Eu enriqueci a pergunta para esclarecer este ponto. (3) Sim, é par e o limite é considerado para que eu não me importe com ímpares .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani

@SureshVenkat: Obrigado por ter melhorado a legibilidade da questão ;-)

Giorgio camerani

Deixe-me dizer que é bem provável que haja resultados de concentração para em gráficos cúbicos aleatórios, o que significa que o valor esperado, o alto valor de probabilidade e assim por diante são todos iguais. A menos que o OP esclareça, acho que uma resposta para qualquer uma dessas perguntas seria uma resposta razoável para essa pergunta.

α (G)

$\alpha(G)$

quer

@ WalterBishop: Deixe-me fazer mais uma pergunta. Como você define se está desconectado?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Respostas:

A amplitude para gráficos de expansão. Um gráfico aleatório 3-regular é assintoticamente quase certamente um gráfico expansor (consulte Wikipedia) , então a expectativa da amplitude será , pois a probabilidade de não ser um gráfico expansor chega a quando vai a . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Para um gráfico expansor com o parâmetro , para qualquer conjunto de vértices com , existem vizinhos do conjunto. Agora, permita que o número de vértices no nível seja , com . Da propriedade de expansão, temos então que, enquanto não for muito grande (por exemplo, ainda não incluímos metade dos vértices) Agora, procure o nível que contém o vértice . Ou seja, então e $\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$ . Se esse nível for grande, ou seja, , estamos prontos. Caso contrário, o próximo nível tamanho e acabamos.

ℓ_{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},$

Embora essa prova analise o número de vértices em um nível, e não o número de arestas (sobre as quais o OP perguntou), sempre há pelo menos tantas arestas adicionadas na etapa quanto vértices no nível , pois cada vértice deve ser atingido por alguma vantagem. $i$ $i$

Peter Shor
fonte

Obrigado pela sua resposta! Isso é muito surpreendente (pelo menos para mim): mesmo se o número total de arestas for , e o número de níveis for , o mais nível lotado ainda possui bordas . Portanto, as arestas não estão espalhadas uniformemente entre os níveis: minha intuição (empírica, incorreta) é que, exceto por alguns níveis iniciais e poucos níveis finais, deveria haver níveis centrais entre os quais as arestas seriam foram espalhados de maneira uniforme.

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

com "empírico" você quer dizer que realmente executou testes? é de cerca de para gráficos aleatórios cúbicos, consulte ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

didest

Sim, eu executei testes de até e medi a quantidade . Se aproximasse de quando aumentasse, isso daria evidências empíricas de que . Cerca de , era cerca de , enquanto cerca de , era cerca de (é claro que nunca considerei esses números como evidência empírica, porque ainda é pequeno demais para representar um assintótico). No entanto, quando eu disse "intuição empírica"

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

... Eu quis dizer um sentimento real (errado) em vez do resultado dos testes: senti que essas BFS deveriam ter uma forma de "salsicha" (ou seja, minúsculas nos extremos e de constante sensação no meio). "Eles têm que ser assim", pensei. A prova acima mostra como minha intuição estava totalmente errada. No entanto, ainda estou surpreso: bordas, níveis, mas não em cada nível.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

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

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

Giorgio Camerani

A resposta de Peter Shor é realmente boa, mas há outra maneira de responder a isso: provar que a largura da árvore é limitada por duas vezes a amplitude (a versão do vértice). Como sabemos que os expansores 3-regulares têm largura de árvore linear, estamos prontos.

Veja a construção de uma decomposição de árvore, dada uma árvore BFS, é o slide 15 desta apresentação: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

É fácil ver que o tamanho de cada bolsa é delimitado por duas vezes o nível mais amplo.

didest
fonte

Obrigado pela sua resposta, essa apresentação foi muito útil.

Giorgio Camerani