Was ist der Beweis für dieses Lemma von Hajnal über die zufällige Abfragekomplexität monotoner Grapheneigenschaften?

8

In diesem Artikel stellt Hajnal das folgende Lemma fest:

Sei die Menge aller zweigeteilten Graphen mit n Eckpunkten im linken Teil und m Eckpunkten im rechten Teil. Angenommen, PG n , m ist nicht trivial, monoton und in Bezug auf zweigliedrige Graphisomorphismen invariant. Ordnen Sie die Menge der Minimalgraphen mit der Eigenschaft P lexikographisch gemäß der sortierten Liste der Grade der linken Eckpunkte und lassen Sie G den ersten Minimalgraphen mit der Eigenschaft P gemäß dieser Reihenfolge sein. Dann randomisierten die Null-Fehler - Abfrage Komplexität von P ist Ω ( Δ LGn,mnmPGn,mPGPP, wobeiΔL(G)der maximale Grad eines Scheitelpunkts auf der linken Seite vonG istundδL(G)der durchschnittliche Grad der Scheitelpunkte auf der linken Seite vonG ist.Ω(ΔL(G)δL(G)n)ΔL(G)GδL(G)G

(Tatsächlich verwendet Hajnal eine geringfügige Erweiterung des obigen Lemmas.) Das gleiche Lemma wird auch von Gröger in diesem anderen Artikel und von Chakrabarti und Khot in diesem anderen Artikel verwendet . Aber ich kann den Beweis für Hajnals Lemma nicht herausfinden. Hajnal schreibt das Lemma Yao zu und zitiert dieses Papier . Aber Yaos Papier behauptet dieses Lemma in dieser Form nicht wirklich.

Yaos Artikel ist ein eng verwandtes Lemma. (Lemma 5 in Yaos Artikel oder gleichwertig Lemma 6 in dieser Journalversion von Yaos Artikel.) Indem ich den Beweis des Lemmas in Yaos Artikel anpasse, sehe ich, wie Hajnals Lemma unter der zusätzlichen Annahme dass δ L ( G ) Ω ist ( 1 ) . Ich habe Probleme mit dem Fall, dass δ L ( G ) subkonstant ist.δL(G)Ω(1)δL(G)

λ(n)δL(G)μ(n)ΔL(G)ΔL(G)4δL(G)4δL(G)n2

δL(G)O(ΔL(G)n)ΔL(G)δL(G)nTi

Wie kann der Beweis gepatcht werden?

William Hoza
quelle
Ω(ΔL(G)δL(G)n)

Antworten:

5

Ω(ΔL(G)δL(G)n)

William Hoza
quelle