Funkcja Lovasz theta i wykresy regularne (w szczególności cykle nieparzyste) - związki z teorią spektralną

Wpis dotyczy: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

Jak dalece Lovasz jest związany ze zdolnością do zerowego błędu regularnych grafów? Czy istnieją przykłady, w których wiadomo, że ograniczenie Lovasz nie jest równe pojemności zerowego błędu zwykłego wykresu? (Oleksandr Bondarenko odpowiedział poniżej).

W szczególności czy znana jest jakakolwiek ścisła nierówność dla nieparzystych cykli boków większych lub równych $7$ ?

Aktualizacja Jakie ulepszenie jest potrzebne w teorii spektralnej, aby poprawić funkcję Lovasz theta, aby można było zmniejszyć różnicę między pojemnością Shannona a Lovaszem Thetą w przypadkach, w których istnieje luka? (Uwaga: martwię się tylko z perspektywy spektralnej)

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

W zaznaczono, że „Najbardziej znane górne granice i dla nieparzystych i większych niż są podane przez funkcję Lovasz theta ...”. Na tej podstawie dochodzę do wniosku, że odpowiedź na twoje ostatnie pytanie brzmi „nie” (od tego czasu nie znam żadnych poprawiających się wyników).$[2]$Θ ( ¯ C m ) $\Theta(C_m)$$\Theta(\overline{C}_m)$$m$$5$

Znalezienie pojemności Shannona nawet dla byłoby dużym przełomem dla tego trudnego problemu. Dodatkowo można to zauważyć$C_7$

„nie wiadomo, czy można rozstrzygnąć problem decydujący o tym, czy pojemność Shannona danego wykresu wejściowego przekracza daną wartość”.

1. W. Haemers, „ O niektórych problemach Lov$\acute{a}$ ostre'a dotyczących pojemności Shannona na wykresie ”, IEEE Trans. w sprawie teorii informacji, vol. 25, nr 2, s. 231–232, marzec 1979 r.
2. T. Bohman, „ Twierdzenie graniczne o pojemności Shannona cykli nieparzystych. II ”, Proceedings of the American Mathematical Society, 2005.
3. N. Alon, „ Kombinatorialne rozumowanie w teorii informacji ”.