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

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, P ⊆ G 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 Ω ( Δ $\mathscr{G}_{n, m}$$n$$m$$\mathscr{P} \subseteq \mathscr{G}_{n, m}$$\mathscr{P}$$G$$\mathscr{P}$$\mathscr{P}$, 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.$\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$$\Delta_L(G)$$G$$\delta_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.$\delta_L(G) \geq \Omega(1)$$\delta_L(G)$

$\lambda(n)$$\delta_L(G)$$\mu(n)$$\Delta_L(G)$$\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$

$\delta_L(G)$$O(\Delta_L(G) n)$$\frac{\Delta_L(G)}{\delta_L(G)} n$$T_i'$

Wie kann der Beweis gepatcht werden?

$\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$