Fungsi Lovasz theta dan grafik reguler (siklus aneh khususnya) - koneksi ke teori spektral

Posting terkait dengan: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

Seberapa jauh Lovasz terikat dari kapasitas nol-kesalahan grafik reguler? Adakah contoh di mana ikatan Lovasz diketahui tidak sama dengan kapasitas nol-kesalahan pada grafik biasa? (Ini dijawab di bawah ini oleh Oleksandr Bondarenko.)

Secara khusus, adakah ketimpangan ketat yang diketahui untuk siklus ganjil sisi lebih besar atau sama dengan $7$ ?

Perbarui Perbaikan apa yang diperlukan dalam teori spektral untuk meningkatkan fungsi Lovasz theta sehingga kesenjangan antara kapasitas Shannon dan Lovasz Theta untuk kasus-kasus yang ada celah dapat diturunkan? (Catatan saya hanya memperhatikan dari perspektif spektral)

$G$$\Theta(G)$$\acute{a}$$\vartheta(G)$$[1]$$\ddot{a}$ $G$$\Theta(G)\leqslant7<\vartheta(G)=9$

Dalam dicatat bahwa "Batas atas yang paling dikenal pada dan untuk aneh dan lebih besar dari diberikan oleh fungsi theta Lovasz ...". Dari sini saya menyimpulkan bahwa jawaban untuk pertanyaan terakhir Anda adalah tidak (sejak saat itu saya tidak tahu hasil apa pun yang membaik tentang ini.).$[2]$$\Theta(C_m)$$\Theta(\overline{C}_m)$$m$$5$

Menemukan kapasitas Shannon bahkan untuk akan menjadi terobosan besar untuk masalah sulit ini. Selain itu, dapat diperhatikan bahwa$C_7$

"Tidak diketahui apakah masalah memutuskan apakah kapasitas Shannon dari grafik input yang diberikan melebihi nilai yang diberikan dapat ditentukan".

1. W. Haemers, " Pada beberapa masalah Lov sz mengenai kapasitas Shannon grafik$\acute{a}$ ," IEEE Trans. tentang Teori Informasi, vol. 25, tidak. 2, hlm. 231–232, Maret 1979.
2. T. Bohman, " Teorema batas untuk kapasitas Shannon dari siklus aneh. II ," Prosiding Masyarakat Matematika Amerika, 2005.
3. N. Alon, " Penalaran Kombinatorial dalam Teori Informasi ".