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