Pertanyaan yang diberi tag expanders

Ekspander adalah grafik jarang (derajat rendah) dengan "pemuaian" tinggi, diukur dengan salah satu dari beberapa cara; biasanya mirip dengan rasio minimum ukuran batas subgraf dengan volume subgraf.

25
Lemma Keteraturan untuk Grafik Jarang

Szemeredi's Regularity Lemma mengatakan bahwa setiap grafik yang padat dapat diperkirakan sebagai penyatuan O ( 1)O(1)O(1) banyak grafik expander bipartit. Lebih tepatnya, ada partisi dari sebagian besar simpul ke dalam O ( 1 )O(1)O(1) set sehingga sebagian besar pasangan membentuk bipartit...