Eine Variation der Diskrepanz mit zufälligen Graphen

9

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+11σ{+1,1}n+1s1nsσiξi(σ)ξi(σ)

N(σ):=i=1n1{ξi(σ)0}.
σN(σ)(maxN)/ns/np (logn)/ndh der durchschnittliche Grad wächst als ). Das Hauptinstrument ist in dem Fall, in dem .logns/n(0,1/2)
Passant51
quelle
1
Ich habe den Titel geändert, weil das, was Sie fragen, mit Diskrepanzproblemen in Bereichsbereichen zusammenhängt. Es ist jedoch NICHT mit Diskrepanzen in Graphen verbunden (was mehr über Abweichungen der
Kantendichte ist
2
einfache Bindung: nimm zufällig; , wobei der Grad des Scheitelpunkts und eine Konstante ist. Also, . Wenn sagen wir und der Graph -regelmäßig ist, dann existiert so dass . σPr[ξi(σ)<0]exp(Cδi(s/n1/2)2)δiiCE[N(σ)]i1exp(Cδi(s/n1/2)2)s=3n/4(16/C)lognσN(σ)nO(1)
Sasho Nikolov
@ Suresh: Danke. Das ist es, was ich mag, wenn ich Informatiker frage, ob Sie etwas Neues lernen! Wo kann man also etwas über Diskrepanzprobleme im Bereichsbereich lernen? (Vielleicht ein kurzes, kurzes Papier?)
Passant51
1
@Sasho: Danke. Aus irgendeinem Grund kann ich die Gleichungen nicht richtig sehen (sie sind mit dem umgebenden Text kollidiert). Ich werde versuchen, sie zu lesen und mich bei Ihnen zu melden. Aber ich sollte erwähnen , dass das interessante Regime ist für mich und das Problem schwieriger zu bekommen scheint s / n nähert sich 1 / 2 . (Dies ist auf die Berücksichtigung der Symmetrie in dem ursprünglichen Problem zurückzuführen, von dem dies stammt.) Ich glaube nicht, dass ein Blick auf ein zufälliges σ dies für s / n ( 0 , 1 / ) tun würdes/n(0,1/2)s/n1/2σ . s/n(0,1/2)
Passant51
Die Vermutung / Hoffnung ist, dass für beispielsweise G (n, p) mit p ( log n ) / n oder p ( log n ) 1 + ϵ / n . Ich habe gerade den Tippfehler in meinem ursprünglichen Beitrag bezüglich p erkannt . Das tut mir leid. Der durchschnittliche Grad wächst als log n nicht p . (maxN)/n=o(1)p (logn)/np (logn)1+ϵ/nplognp
Passant51

Antworten:

8

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.logn

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.

Abraham D Flaxman
quelle
Dies als CSP zu betrachten, scheint in der Tat besser zu passen, als es als Diskrepanzproblem zu betrachten
Sasho Nikolov
Vielen Dank. Das sieht sehr interessant aus. Ich werde es mir ansehen.
Passant51
3

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 σmS1,,Sm{1,n}=[n]minσ:[n]{±1}maxj|iSjσ(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.σ(Sj)=|iSjσ(i)|σ(Sj)σ(Sj)

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/2G=([n],E)δ1,,δnσs 1σ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 ( s)E[ξi(σ)]=δis/nPr[ξi(σ)<0]exp(Cδi(s/n1/2)2)C . Es gibt also einigeσ, die diese Grenze erreichen.E[N(σ)]niexp(Cδi(s/n1/2)2)σ

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σσsξi(σ)δi(2s/n1)δi für einige C und η ( n ) ein Fehlerparameter aus dem zentralen Grenzwertsatz. Wir sollten n η ( n ) = o ( n ) haben , damit Sie N ( σ ) i nehmen könnenPr[ξi(σ)0]=exp(Cδi(2s/n1)2)±η(n)η(n)nη(n)=o(n) .N(σ)iexp(Cδi(2s/n1)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.δis/nn/2

Sasho Nikolov
quelle
Vielen Dank für die netten Links und das Argument. Ich mag das probabilistische Argument, aber ich denke, mit Ihrer Bindung stimmt etwas nicht. Sie können dies sehen, indem Sie , für die wir P r [ ξ i ( σ ) < 0 ] = 1 haben sollten . Es scheint, dass dies falsch gelaufen ist: Wenn Sie σ gleichmäßig zufällig aus der im Problem angegebenen Menge auswählen , hat jedes σ j prob. γ : = s / n von + 1 und prob. von 1 - γs=0Pr[ξi(σ)<0]=1σσjγ:=s/n+11γdes Seins . Daher E [ ξ i ( σ ) ] = ( 2 γ - 1 ) δ i , die negativ für ist γ ( 0 , 1 / 2 ) ...1E[ξi(σ)]=(2γ1)δiγ(0,1/2)
passerby51
Das wird nicht unabhängig sein und streng genommen können wir nicht sagen, Hoeffding-Ungleichung. Aber lassen Sie uns dieses kleine Detail ignorieren und annehmen, dass iid Dann wäre die Grenze P r [ 1{σj}die fürgiltt0. Wir könnent=2γ-1<0nicht setzen, umPr[ξi(σ)<0] zu erhalten. Pr[1δiξi(σ)<t+2γ1)exp(δit2/2)t0t=2γ1<0Pr[ξi(σ)<0]
Passant51
Entschuldigung, ich hätte das spezifizieren sollen: Die Annahme hier war, dass . Andernfalls macht dies keinen Sinn und Sie brauchen etwas Stärkeres wie Berry-Esseen. Ich denke, das σ j kann als im Wesentlichen unabhängig angenommen werdens>n/2σj
Sasho Nikolov
@ passerby51 eine Skizze hinzugefügt , wie Sie eine quantitative Version des zentralen Grenzwertsatzes zu verwenden , könnten versuchen , die probabilistischen zu gebunden zu verlängern . s/n<1/2
Sasho Nikolov