Amplituda losowych wykresów sześciennych

Rozważ dołączony losowy wykres sześcienny $G=(V,E)$ z $n =|V|$ wierzchołki narysowane z $G(n, 3$ reg $)$ (jak tu zdefiniowano , tzn. $3n$ jest parzyste, a dowolne dwa wykresy mają takie samo prawdopodobieństwo).

Oczywiście istnieje $n$ możliwe Szerokość najpierw szuka, po jednej dla każdego węzła wyjściowych $s \in V$ . Przeszukiwanie wszerz $B_G$ zaczynając od węzła $s \in V$ cesjonariusze poziom A $d(s, v)$ dla każdego węzła $v \in V$ , w którym $d(s, v)$ jest odległością pomiędzy $s$ i $v$ w $G$ .

$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$

Biorąc pod uwagę konkretną szerokość pierwszego wyszukiwania , niech będzie liczbą krawędzi, które mają przypisany poziom , i niech . Innymi słowy to liczba krawędzi poziomu zawierających więcej krawędzi niż jakikolwiek inny poziom. Ostatecznie, niech jest maksymalna dla każdego z Szerokość pierwszych przeszukiwania . $B_G$ $\alpha(B_G,i)$ $i$ $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ $\alpha(B_G)$ $\alpha(G)$ $\alpha(B_G)$ $n$ $G$

Nazwijmy na amplitudę z . $\alpha(G)$ $G$

Pytanie

Jak rośnie oczekiwana wartość gdy dąży do nieskończoności? Przypomnij sobie, że jest losową sześcienną . Dokładniej, naprawdę chciałbym wiedzieć, czy oczekiwana wartość należy do . $\alpha(G)$ $n$ $G$ $\alpha(G)$ $o(n)$

Ponieważ jest parzyste, limit jest brany pod uwagę, więc nie dbam o nieparzyste . $n$ $n$

graph-theory co.combinatorics Giorgio Camerani
źródło

(1) Proszę określić, z którego rozkładu prawdopodobieństwa rysuje się wykres sześcienny. (2) Czy interesuje Cię oczekiwanie na jako funkcję lub coś innego? (3) Przypuszczam, że jest parzyste (w przeciwnym razie wykres sześcienny nie istnieje). Więc przypuszczam, że limit jest brany pod uwagę, abyś nie przejmował się nieparzystymi liczbami „ ”.

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto,

@YoshioOkamoto: (1) Z reg jak zdefiniowano w stanford.edu/class/msande337/notes/… ( jest parzyste, a dowolne dwa wykresy mają takie samo prawdopodobieństwo). (2) Wzbogaciłem pytanie, aby wyjaśnić tę kwestię. (3) Tak, jest parzyste, a limit jest brany pod uwagę, aby nie obchodziły mnie nieparzyste .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani,

@SureshVenkat: Dziękujemy za poprawę czytelności pytania ;-)

Giorgio Camerani

Pozwól mi powiedzieć, że jest całkiem prawdopodobne, że wyniki stężenia dla na losowych wykresach sześciennych, co oznacza, że oczekiwana wartość, wartość wysokiego prawdopodobieństwa itd. Są takie same. Jeśli OP nie wyjaśni tego, uważam, że odpowiedź na którekolwiek z tych pytań byłaby rozsądną odpowiedzią na to pytanie.

α (G)

$\alpha(G)$

Peter Shor,

@WalterBishop: Pozwól, że zadam jeszcze jedno pytanie. Jak zdefiniować jeśli jest odłączony?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Odpowiedzi:

Amplituda dla wykresów ekspanderów. Losowy 3-regularny wykres jest asymptotycznie prawie na pewno grafem ekspandera (patrz Wikipedia) , więc oczekiwanie amplitudy będzie , ponieważ prawdopodobieństwo, że nie jest to wykres ekspandera, wynosi gdy idzie do . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Dla wykresu ekspandera z parametrem , dla dowolnego zestawu wierzchołków z , są sąsiedzi zestawu . Teraz niech liczba wierzchołków na poziomie będzie , gdzie . Następnie mamy z właściwości że dopóki nie jest zbyt duży (tj. Nie zawarliśmy jeszcze połowy wierzchołków) Teraz poszukaj poziomu który zawiera wierzchołek . To znaczy, więc i $\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$ . Jeśli ten poziom jest duży, tj. , jesteśmy skończeni. W przeciwnym razie następny poziom ma rozmiar i skończyliśmy.

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

Chociaż ten dowód dotyczy liczby wierzchołków na poziomie, a nie liczby krawędzi (o które poprosił PO), zawsze jest co najmniej tyle krawędzi dodanych w kroku ile wierzchołków na poziomie , ponieważ każdy wierzchołek musi zostać osiągnięty o jakąś przewagę. $i$ $i$

Peter Shor
źródło

Dzięki za odpowiedź! Jest to bardzo zaskakujące (przynajmniej dla mnie): nawet jeśli całkowita liczba krawędzi wynosi , a liczba poziomów to , najwięcej zatłoczony poziom ma wciąż krawędzie. Zatem krawędzie nie są rozrzucone równomiernie między poziomami: moja (empiryczna, błędna) intuicja była taka, że oprócz kilku poziomów początkowych i kilku poziomów końcowych powinny istnieć poziomy centralne, wśród których krawędzie byłyby zostały rozrzucone nieco równomiernie.

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,

„empiryczny” oznacza, że faktycznie przeprowadziłeś testy? wynosi około dla losowych wykresów sześciennych, patrz ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

zrobił

Tak, przeprowadziłem testy od do i zmierzyłem ilość . Gdyby zbliżył się do gdy wzrosło, dałoby to empiryczny dowód, że . Około , było około , podczas gdy około , było około (oczywiście nigdy nie uważałem tych liczb za dowody empiryczne, ponieważ jest wciąż zbyt małe, aby reprezentować asymptotyczny). Kiedy jednak powiedziałem „intuicja empiryczna”

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,

... Miałem na myśli prawdziwe (złe) odczucie, a nie wynik testu: poniekąd czułem, że te BFS muszą mieć kształt „kiełbasy” (tj. Malutki na krańcach i ciągłego łaskotania w środku). „Muszą tak być” - pomyślałem. Powyższy dowód pokazuje, jak prosta była moja intuicja. Niemniej jednak wciąż jestem zaskoczony: edge, poziomy, ale nie na każdym poziomie.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

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

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

Giorgio Camerani,

Odpowiedź Petera Shora jest naprawdę dobra, ale jest na to inny sposób: udowodnienie, że szerokość jest ograniczona górną granicą dwukrotności amplitudy (wersja wierzchołkowa). Ponieważ wiemy, że 3-regularne ekspandery mają szerokość liniową, jesteśmy skończeni.

Zobacz budowę rozkładu drzewa na podstawie drzewa BFS, jest to slajd 15 tej prezentacji: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Łatwo zauważyć, że rozmiar każdej torby jest ograniczony górną dwukrotnością najszerszego poziomu.

didest
źródło

Dziękuję za odpowiedź, ta prezentacja była bardzo pomocna.

Giorgio Camerani,