Saya mencari teorema yang mengatakan sesuatu seperti ini: jika waktu tutup rantai Markov reversibel kecil, maka celah spektral besar. Di sini celah spektral berarti , yaitu, kami mengabaikan nilai eigen terkecil dari rantai.
Secara intuitif, tampaknya sangat masuk akal bahwa jika Anda dapat menutupi semua simpul grafik dengan cepat, maka waktu pencampuran harus kecil. Secara khusus, jika Anda dapat mencakup semua simpul grafik dalam waktu , tentunya Anda harus dapat mengesampingkan kesenjangan spektral, katakanlah, ?
Salah satu hambatan yang mungkin akan mematahkan implikasi antara waktu tutupan kecil dan kesenjangan spektral besar adalah bipartiteness: pada grafik bipartit, Anda dapat memiliki waktu tutupan kecil dengan nilai eigen . Dengan dalam pertanyaan saya, saya melewati masalah ini dengan mengabaikan nilai eigen terkecil.
sumber