Artikel - Menyelesaikan Taruhan 35 Tahun: Seberapa Umum Graf Ramanujan?

Princeton, New Jersey, Amerika Serikat - Pada akhir 1980-an, Noga Alon dan Peter Sarnak bertaruh tentang seberapa umum graf ekspander terbaik, yang disebut graf Ramanujan. Sarnak berpendapat bahwa graf ini langka, sementara Alon berpendapat bahwa graf ini umum. Setelah lebih dari tiga dekade, tiga matematikawan akhirnya menemukan jawabannya.

Graf ekspander digunakan dalam berbagai aplikasi seperti pemodelan otak dan kode koreksi kesalahan. Graf Ramanujan adalah graf ekspander terbaik yang mencapai batas Alon-Boppana. Namun, membangun graf ini sangat sulit dan membutuhkan hasil dari teori bilangan.

Horng-Tzer Yau dan kolaboratornya memperluas konjektur universalitas Wigner ke graf reguler, yang memungkinkan mereka menghitung distribusi nilai eigen. Mereka menemukan bahwa sekitar 69% graf reguler adalah graf Ramanujan, membuat graf ini tidak terlalu umum tetapi juga tidak langka. Ini menyelesaikan taruhan antara Alon dan Sarnak.

Pertanyaan Terkait

Apa yang menjadi fokus utama debat antara Noga Alon dan Peter Sarnak?

Fokus utama debat antara Noga Alon dan Peter Sarnak adalah mengenai kelangkaan graf ekspander yang optimal.

Apa itu graf ekspander dan mengapa penting dalam matematika?

Graf ekspander adalah jenis graf yang memiliki sedikit tepi tetapi sangat terhubung, penting untuk model otak, analisis statistik, dan kode koreksi kesalahan.

Siapa yang berhasil membuktikan konjektur universalis untuk graf reguler?

Horng-Tzer Yau berhasil membuktikan konjektur universalis untuk graf reguler.

Apa hasil akhir dari taruhan antara Alon dan Sarnak mengenai graf Ramanujan?

Hasil akhir dari taruhan antara Alon dan Sarnak menunjukkan bahwa sekitar 69% dari graf reguler adalah graf Ramanujan, menjadikannya tidak umum dan tidak langka.

Mengapa graf Ramanujan dianggap sulit untuk dibangun?

Graf Ramanujan dianggap sulit untuk dibangun karena kompleksitas matematis yang terlibat dalam konstruksinya.