Apa bukti dari lemma ini oleh Hajnal tentang kompleksitas kueri acak dari properti grafik monoton?

Dalam tulisan ini , Hajnal menyatakan lemma berikut:

Misalkan $\mathscr{G}_{n, m}$ adalah himpunan semua grafik bipartit dengan simpul di bagian kiri dan simpul di bagian kanan. Misalkan adalah nontrivial, monoton, dan invarian terkait dengan isomorfisme grafik bipartit. Pesan rangkaian grafik minimal dengan properti leksikografis sesuai dengan daftar derajat sudut kiri yang diurutkan, dan biarkan G menjadi grafik minimal pertama dengan properti P menurut urutan ini. Maka kompleksitas query acak nol-kesalahan dari P adalah Ω ( Δ L ( G$n$$m$$\mathscr{P} \subseteq \mathscr{G}_{n, m}$$\mathscr{P}$$G$$\mathscr{P}$$\mathscr{P}$, di manaΔL(G)adalah tingkat maksimum simpul apapun dalam sisi kiriGdanδL(G)adalah derajat rata-rata simpul di sisi kiriG.$\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$$\Delta_L(G)$$G$$\delta_L(G)$$G$

(Faktanya, Hajnal sebenarnya menggunakan sedikit ekstensi lemma di atas.) Lemma yang sama juga digunakan oleh Gröger di makalah lain ini dan oleh Chakrabarti dan Khot di makalah lain ini . Tetapi saya tidak dapat menemukan bukti lemma Hajnal. Hajnal menghubungkan lemma dengan Yao dan mengutip makalah ini . Tetapi kertas Yao sebenarnya tidak mengklaim lemma itu dalam bentuk itu.

Makalah Yao memang membuktikan lemma terkait erat. (Lemma 5 di koran Yao, atau setara dengan Lemma 6 di versi jurnal kertas Yao ini .) Dengan mengadaptasi bukti lemma di kertas Yao, saya melihat bagaimana membuktikan lemma Hajnal dengan asumsi tambahan bahwa . Saya mengalami masalah dengan kasus bahwa δ L ( G ) tidak konstan.$\delta_L(G) \geq \Omega(1)$$\delta_L(G)$

(Sekarang saya akan berasumsi bahwa pembaca akrab dengan bukti Yao.) Pemahaman saya adalah bahwa untuk membuktikan lemma Hajnal, idenya adalah untuk memodifikasi bukti Yao dengan dasarnya hanya mengganti dengan δ L ( G ) dan μ ( n ) dengan Δ L ( G ) di mana-mana. Pada tingkat tinggi, dengan modifikasi ini, penalaran Yao masih masuk akal, dan menunjukkan bahwa untuk "menemukan cukup sisi yang hilang", algoritma kueri harus membuat setidaknya tentang Δ L ( G ) - 4 δ L$\lambda(n)$$\delta_L(G)$$\mu(n)$$\Delta_L(G)$ pertanyaan.$\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$

Masalahnya adalah bahwa ketika adalah subconstant, karena operasi langit-langit, yang batas bawah hanya O ( Δ L ( G ) n ) , yang jauh lebih kecil dari terikat Δ L ( G $\delta_L(G)$$O(\Delta_L(G) n)$yang muncul di lemma Hajnal. (Secara konkret, masalahnya adalah bahwa setiap setT ′ i perlu memiliki jumlah simpul bilangan bulat di dalamnya.)$\frac{\Delta_L(G)}{\delta_L(G)} n$$T_i'$

Bagaimana bukti bisa ditambal?

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