Odmiana rozbieżności dotycząca losowych wykresów

Załóżmy, że mamy do wykresu na węzłów. Chcielibyśmy przypisać do każdego węzła lub . Nazwij to konfiguracją . Liczba s, które musimy przypisać, to dokładnie (stąd liczba s to .) Biorąc pod uwagę konfiguracji , patrzymy na każdy węzeł i sumujemy wartości przypisane jego sąsiadom, wywołanie to . Następnie liczbę węzłów, dla których jest nieujemna: $n$ $+1$ $−1$ $\sigma \in \{+1,−1\}^n$ $+1$ $s$ $−1$ $n−s$ $\sigma$ $i$ $\xi_i(\sigma)$ $\xi_i(\sigma)$

N (σ) := \sum_{i = 1}^{n} 1 {ξ_{i} (σ) \geq 0} .

$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$ Pytanie brzmi: jaka jest konfiguracja która maksymalizuje ? Co ważniejsze, czy możemy podać ograniczenie w kategoriach

. Zastanawiam się, czy ten problem wydaje się każdemu znany, czy też można go sprowadzić do znanego problemu w teorii grafów. Jeśli to pomaga, można założyć, że wykres jest losowy typu Erdősa-Renyi (powiedzmy, G (n, p) z prawdopodobieństwem krawędzi

, tj. Średni stopień rosnący jako

). Główny instrest ma miejsce w przypadku, gdy

σ

$\sigma$

N (σ)

$N(\sigma)$

(max N) / n

$(\max N)/n$

s / n

$s/n$

p (\log n) / n

$p ~ (\log n)/n$

\log n

$\log n$

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

graph-theory co.combinatorics optimization passerby51
źródło

Zmieniłem tytuł, ponieważ to, o co pytasz, dotyczy problemów z rozbieżnościami w przestrzeniach zasięgu. NIE jest to jednak związane z rozbieżnością na wykresach (która dotyczy bardziej odchyleń gęstości krawędzi)

Suresh Venkat

prosta granica: weź losowo; , gdzie jest stopniem wierzchołka a jest pewną stałą. Zatem . Jeśli powiedzmy a wykres to nieregularny, to istnieje taki, że .

σ

$\sigma$

Pr [ξ_{i} (σ) < 0] \leq \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$

δ_{i}

$\delta_i$

i

$i$

C

$C$

E [N (σ)] \geq \sum_{i} 1 - \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$E[N(\sigma)] \geq \sum_i{1-\exp(-C\delta_i (s/n - 1/2)^2)}$

s = 3 n / 4

$s = 3n/4$

(16 / C) \log n

$(16/C)\log n$

σ

$\sigma$

N (σ) \geq n - O (1)

$N(\sigma) \geq n - O(1)$

Sasho Nikolov

@Suresh: Dzięki. Właśnie to lubię pytać informatyków, uczysz się czegoś nowego! Więc gdzie jest dobre miejsce, aby dowiedzieć się o problemach z rozbieżnościami w przestrzeni zasięgu? (Może krótki zwięzły artykuł?)

przechodzień51

@Sasho: Dzięki. Z jakiegoś powodu nie widzę poprawnie równań (kolidowały z otaczającym tekstem). Spróbuję je przeczytać i skontaktuję się z Tobą. Ale powinienem wspomnieć, że interesującym dla mnie reżimem jest i problem wydaje się narastać, gdy zbliża się do . (Wynika to z rozważenia symetrii w pierwotnym problemie, z którego pochodzi.) Nie sądzę, aby spojrzenie na losową zrobiłoby to dla .

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

s / n

$s/n$

1 / 2

$1/2$

σ

$\sigma$

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

passerby51

Domyślamy się, że dla powiedzmy G (n, p) z lub . Właśnie zdałem sobie sprawę z literówki w moim oryginalnym poście dotyczącym . Przepraszam za to. Średni stopień rośnie, ponieważ nie .

(max N) / n = o (1)

$(\max N)/n = o(1)$

p (\log n) / n

$p ~ (\log n) / n$

p (\log n)^{1 + ϵ} / n

$p ~ (\log n)^{1+\epsilon} /n$

p

$p$

\log n

$\log n$

p

$p$

passerby51

Odpowiedzi:

Można do tego podejść za pomocą metody „drugiej chwili”, podobnej do tej, którą zastosowałem w ostrym progu dla problemu satysfakcji z ograniczeń losowych , Discrete Mathematics 285 / 1-3 (2004), 301-305.

Gdy średni stopień rośnie jak wystarczająco duże stałe czasy , takie podejście często wystarczało, aby dokładnie określić próg satysfakcji. Mogłoby to również pokazać fragment klauzul, które można spełnić w niezadowalającym przypadku, chociaż nie zbadałem tego. $\log n$

Aby twój problem bardziej przypominał mój ogólny, możesz go postrzegać jako „MAX-AT-LEAST-HALF-SAT” ze specjalną strukturą graficzną leżącą u podstaw klauzul we wzorze CNF. Nie sądzę jednak, aby ta specjalna struktura pomogła w analizie najgorszego przypadku, a ponieważ rozmiar klauzuli jest nierównomierny, a zestaw „złych” przydziałów rośnie, będziesz musiał przejść przez obliczenia i sprawdzić, czy nadal działa.

Abraham D. Flaxman
źródło

postrzeganie tego jako CSP wydaje się rzeczywiście lepszym rozwiązaniem niż postrzeganie go jako problemu rozbieżności

Sasho Nikolov

Dziękuję Ci. To wygląda bardzo interesująco. Zapoznam się z tym.

passerby51

Pozwól mi rozwinąć mój komentarz. Po pierwsze, jest to podobne do rozbieżności, ale oczywiście różni się na kilka sposobów. Biorąc pod uwagę system zestawów , rozbieżność systemu wynosi . Oznaczmy. Twoja definicja różni się tym, że chcesz wiedzieć, dla ilu zestawów jest dodatnia, a rozbieżność pyta, jak duża jest w najgorszym przypadku. Krótkie wprowadzenie może może pomóc moje notatki pisarskie . Chazelle ma fajną książkę, która zawiera wiele szczegółów. $m$ $S_1, \ldots, S_m \subseteq \{1, \ldots n\} = [n]$ $\min_{\sigma:[n] \rightarrow \{\pm 1\}}{\max_{j}{|\sum_{i \in S_j}{\sigma(i)}|}}$ $\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$ $\sigma(S_j)$ $\sigma(S_j)$

Dla łatwej probabilistycznej dolnej granicy, gdy , jak w moim komentarzu, biorąc pod uwagę wykres z sekwencją stopni , możesz wybrać jednolicie losowo ze wszystkich sekwencji z ( nie są niezależne, ale w tym przypadku powinno być również możliwe udowodnienie ograniczenia Chernoffa). Mamy a przy ograniczeniu Chernoffa dla pewnej stałej . Więc . Istnieje więc pewna $s > n/2$ $G = ([n], E)$ $\delta_1, \ldots, \delta_n$ $\sigma$ $s$ $1$ $\sigma_i$ $E[\xi_i(\sigma)] = \delta_i s/n$ $\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$ $C$ $E[N(\sigma)] \geq n - \sum_i{\exp(-C\delta_i (s/n - 1/2)^2)}$ $\sigma$ która osiąga tę granicę.

EDYCJA: Wydaje się, że jesteś zainteresowany sprawą . Wybierzmy losowo w taki sam sposób, jak w poprzednim akapicie. Używając wersji centralnego twierdzenia granicznego dla próbkowania bez zamiany ( jest próbką rozmiaru bez zamiany z wierzchołków wykresu), powinieneś być w stanie pokazać, że zachowuje się jak średnia Gaussa i wariancja dotycząca , więc dla niektórych C i parametr błędu z centralnego twierdzenia granicznego. Powinniśmy mieć $s < n/2$ $\sigma$ $\sigma$ $s$ $\xi_i(\sigma)$ $\delta_i (2s/n - 1)$ $\delta_i$ $\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$ $\eta(n)$ $n\eta(n) = o(n)$ , więc możesz wziąć . $N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

Zastrzeżenia: ma to znaczenie tylko wtedy, gdy są stałe / małe lub jest bardzo bliskie . Również obliczenia są nieco heurystyczne i niezbyt starannie wykonane. $\delta_i$ $s/n$ $n/2$

Sasho Nikolov
źródło

Dziękuję za miłe linki i kłótnię. Podoba mi się argument probabilistyczny, ale myślę, że coś jest nie tak z twoim ograniczeniem. Możesz to zobaczyć, ustawiając , dla którego powinniśmy mieć . Wygląda na to, że coś poszło nie tak: jeśli wybierzesz losowo równomiernie ze zbioru określonego w problemie, każdy ma . bycia i prob. z bycia . Stąd co jest ujemne dla ...

s = 0

$s = 0$

P r [ξ_{i} (σ) < 0] = 1

$Pr[\xi_i(\sigma) < 0] = 1$

σ

$\sigma$

σ_{j}

$\sigma_j$

γ := s / n

$\gamma := s/n$

+ 1

$+1$

1 - γ

$1-\gamma$

- 1

$-1$

E [ξ_{i} (σ)] = (2 γ - 1) δ_{i}

$E[ \xi_i(\sigma)] = (2\gamma-1) \delta_i$

γ \in (0, 1 / 2)

$\gamma \in (0,1/2)$

passerby51

nie będzie niezależny i ściśle rzecz biorąc nie możemy używać powiedzieć Hoeffding nierówności. Ale zignorujmy ten drobny szczegół i załóżmy, że w ten sposób granica byłaby która obowiązuje dla . Nie możemy ustawić aby uzyskać .

{σ_{j}}

$\{\sigma_j\}$

P r [\frac{1}{δ_{i}} ξ_{i} (σ) < - t + 2 γ - 1) \leq \exp (- δ_{i} t^{2} / 2)

$Pr[ \frac{1}{\delta_i} \xi_i(\sigma) < -t + 2\gamma - 1) \le \exp ( -\delta_i t^2/2)$

t \geq 0

$t \ge 0$

t = 2 γ - 1 < 0

$t = 2\gamma - 1 < 0$

P r [ξ_{i} (σ) < 0]

$Pr[\xi_i(\sigma) <0]$

passerby51

przepraszam, powinienem był to określić: założenie było takie, że . w przeciwnym razie nie ma to sensu i potrzebujesz czegoś silniejszego, jak Berry-Esseen. myślę, że można uznać za zasadniczo niezależny

s > n / 2

$s > n/2$

σ_{j}

$\sigma_j$

Sasho Nikolov

@ passerby51 dodał szkic, w jaki sposób możesz spróbować użyć ilościowej wersji twierdzenia o limicie centralnym, aby rozszerzyć prawdopodobieństwo probabilistyczne do .

s / n < 1 / 2

$s/n < 1/2$

Sasho Nikolov