Eine Variation der Diskrepanz mit zufälligen Graphen

Angenommen, wir haben ein Diagramm auf Knoten. Wir möchten jedem Knoten entweder eine oder eine zuweisen . Nennen Sie dies eine Konfiguration . Die Anzahl von s, die wir zuweisen müssen, ist genau (daher ist die Anzahl von s ). Bei einer Konfiguration σ betrachten wir jeden Knoten i und summieren die seinen Nachbarn zugewiesenen Werte. Rufen Sie dies auf ξ i ( σ ) . Wir zählen dann die Anzahl der Knoten, für die ξ i ( σ ) nicht negativ ist: N.$n$$+1$$−1$$\sigma \in \{+1,−1\}^n$$+1$$s$$−1$$n−s$$\sigma$$i$$\xi_i(\sigma)$$\xi_i(\sigma)$

Man könnte dies mit einer „zweiter Momentenmethode“ Berechnung, ähnlich den Ansatz ich verwenden für ein zufälliges Constraint Satisfaction Problem ais Schwelle , Discrete Mathematics 285 / 1-3 (2004), 301-305.

Wenn der durchschnittliche Grad wie eine ausreichend große konstante Zeit wächst , war dieser Ansatz oft ausreichend, um genau die Schwelle der Erfüllbarkeit zu finden. Es könnte möglicherweise auch den Bruchteil der Klauseln zeigen, die in einem unbefriedigenden Fall erfüllt werden können, obwohl ich das nicht untersucht habe.$\log n$

Damit Ihr Problem eher meinem allgemeinen ähnelt, können Sie es als "MAX-AT-LEAST-HALF-SAT" mit einer speziellen grafischen Struktur betrachten, die den Klauseln in der CNF-Formel zugrunde liegt. Ich denke jedoch nicht, dass diese spezielle Struktur bei einer Worst-Case-Analyse hilfreich sein wird. Da Ihre Klauselgröße uneinheitlich ist und Ihre "schlechte" Zuweisung wächst, müssen Sie die Berechnung durchgehen und prüfen, ob dies der Fall ist funktioniert noch.

Lassen Sie mich auf meinen Kommentar näher eingehen. Erstens ähnelt dies der Diskrepanz, unterscheidet sich jedoch natürlich in mehrfacher Hinsicht. Bei einem System von Mengen S 1 , … , S m ⊆ { 1 , … n } = [ n ] beträgt die Diskrepanz des Systems min σ : [ n ] → { ± 1 } max j | ∑ i ∈ S j σ ( i ) | . Bezeichnen wir $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)}|}}$. Ihre Definition unterscheidet sich darin, dass Sie wissen möchten, für wie viele Mengen σ ( S j ) positiv ist, und die Diskrepanz fragt, wie groß dieGröße von σ ( S j ) im schlimmsten Fall ist. Für eine kurze Einführung können vielleicht meineSchreibernotizenhelfen. Chazelle hat ein schönesBuch, das sehr detailliert ist.$\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$$\sigma(S_j)$$\sigma(S_j)$

Für eine einfache probabilistische Untergrenze, wenn , wie in meinem Kommentar, wenn ein Graph G = ( [ n ] , E ) mit der Gradfolge δ 1 , … , δ n gegeben ist , können Sie σ gleichmäßig zufällig aus allen auswählen Sequenzen mit s 1 's (die σ i sind nicht unabhängig, aber es sollte auch in diesem Fall möglich sein, eine Chernoff-Bindung zu beweisen). Wir haben E [ ξ i ( σ ) ] $s > n/2$$G = ([n], E)$$\delta_1, \ldots, \delta_n$$\sigma$$s$ $1$$\sigma_i$ und durch eine Chernoff gebunden, Pr [ ξ i ( σ ) < 0 ] ≤ exp ( - C δ i ( s / n - 1 / 2 ) 2 ) für eine Konstante C . Also ist E [ N ( σ ) ] ≥ n - ∑ i exp ( - C δ 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$ . Es gibt also einigeσ, die diese Grenze erreichen.$E[N(\sigma)] \geq n - \sum_i{\exp(-C\delta_i (s/n - 1/2)^2)}$$\sigma$

EDIT: Scheint, dass Sie an dem Fall interessiert sind . Lassen Sie uns σ auf die gleiche Weise wie im vorherigen Absatz zufällig auswählen . Wenn Sie eine Version des zentralen Grenzwertsatzes für die ersatzlose Abtastung verwenden ( σ ist eine Stichprobe der Größe s ohne Ersetzung aus den Eckpunkten des Diagramms), sollten Sie zeigen können, dass sich ξ i ( σ ) wie ein Gaußscher Wert mit dem Mittelwert δ i verhält ( 2 s / n - 1 ) und Varianz um δ i , also Pr $s < n/2$$\sigma$$\sigma$$s$$\xi_i(\sigma)$$\delta_i (2s/n - 1)$$\delta_i$ für einige C und η ( n ) ein Fehlerparameter aus dem zentralen Grenzwertsatz. Wir sollten n η ( n ) = o ( n ) haben , damit Sie N ( σ ) ≥ ∑ $\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$$\eta(n)$$n\eta(n) = o(n)$ .$N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

Haftungsausschluss: Dies ist nur dann sinnvoll, wenn konstant / klein ist oder s / n sehr nahe an n / 2 liegt . Auch die Berechnungen sind etwas heuristisch und nicht sehr sorgfältig durchgeführt.$\delta_i$$s/n$$n/2$