Generalisasi yang seimbang dari teorema Hall

Mari dan menjadi set, dan menjadi partisi . Saya ingin membuktikan bahwa ada distribusi lebih dari yang marginalnya seragam lebih dari , dan sedemikian rupa sehingga distribusi lebih dari diinduksi oleh memiliki entropi besar ( distribusi terakhir didefinisikan dengan menetapkan setiap massa probabilitas total elemen bawah ). Kita dapat menggunakan kondisi berikut:Y B X × Y D X × Y X B D B ∈ B B $X$$Y$$\mathcal{B}$$X \times Y$$\mathcal{D}$$X \times Y$$X$$\mathcal{B}$$\mathcal{D}$$B∈\mathcal{B}$$B$$\mathcal{D}$

Perhatikan grafik bipartit yang sisi-sisinya dan , sehingga untuk masing-masing ada tepi dalam (beberapa sisi mungkin). Kemudian, setiap set ukuran setidaknyamemiliki setidaknyatetangga di G.X B ( x , y ) ∈ B ( x , B ) G x $G$$X$$\mathcal{B}$$(x,y) \in B$$(x,B)$$G$$x$$\frac{3}{4}|X|$$\frac{1}{100}|B|$

Saya akan sangat menghargai jika seseorang dapat merujuk saya ke teorema yang relevan. Pertanyaan ini dapat dilihat dalam arti sebagai generalisasi teorema Hall, di mana kondisi di atas adalah kondisi relaksasi Hall, dan di mana alih-alih mendapatkan pasangan yang cocok, kita mendapatkan seperangkat tepi yang subgraf yang sesuai kira-kira teratur.

Latar belakang : Motivasi untuk pertanyaan ini berasal dari kompleksitas komunikasi. Dalam pengaturan kompleksitas komunikasi, dua pemain, Alice dan Bob, masing-masing mendapatkan input dan , dan berinteraksi untuk menghitung beberapa fungsi . Di sini, setiap set terdiri dari pasangan yang menghasilkan transkrip komunikasi yang sama antara Alice dan Bob, dan saya ingin membuktikan bahwa dalam kondisi tertentu, seseorang dapat menemukan distribusi melalui sedemikian rupa sehingga Alice mendapat input yang didistribusikan secara seragam, dan sedemikian rupa sehingga entropi transkrip di bawah distribusi tersebut besar.y f ( x , y ) B ∈ B ( x , y ) X × $x$$y$$f(x,y)$$B \in \mathcal{B}$$(x,y)$$X \times Y$

Anda mungkin melihat ke dalam konsep -faktor dan teorema khusus Tutte tentang keberadaan -faktor. Anda mungkin menemukan Proposisi 2 makalah ini relevan.$f$$f$