Тэта-функция Ловаша и регулярные графы (в частности, нечетные циклы) - связи со спектральной теорией

Сообщение связано с: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

Насколько далеко Lovasz связан с пропускной способностью регулярных графов с нулевой ошибкой? Есть ли примеры, когда известно, что оценка Ловаша не равна емкости регулярного графа с нулевой ошибкой? (Ответил ниже Александр Бондаренко.)

В частности, известно ли строгое неравенство для нечетных циклов сторон, больших или равных $7$ ?

Обновление Какие улучшения необходимы в спектральной теории для улучшения тэта-функции Ловаша, чтобы можно было уменьшить разрыв между емкостью Шеннона и тэтом Ловаша для случаев, когда существует разрыв? (Обратите внимание, я обеспокоен только со спектральной точки зрения)

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

В отмечается, что «Самые известные верхние оценки и для нечетного и большего задаются тэта-функцией Ловаша ...». Из этого я делаю вывод, что ответ на ваш последний вопрос - нет (с тех пор я не знаю каких-либо улучшений по этому вопросу).Θ ( C m ) Θ ( ¯ C m ) m $[2]$$\Theta(C_m)$$\Theta(\overline{C}_m)$$m$$5$

Поиск емкости Шеннона даже для был бы серьезным прорывом для этой сложной проблемы. Кроме того, можно заметить, что$C_7$

«неизвестно, может ли быть решена проблема определения, превышает ли емкость Шеннона заданного входного графа заданное значение».

1. У. Хемерс, “ О некоторых проблемах Lov$\acute{a}$ sharp sz, касающихся емкости графа Шеннона ”, IEEE Trans. по теории информации, вып. 25, нет 2, с. 231–232, март 1979 г.
2. Т. Боман, " Предельная теорема для емкостей Шеннона нечетных циклов. II ", Труды Американского математического общества, 2005.
3. Н. Алон, " Комбинаторные рассуждения в теории информации ".