Função teta de Lovasz e gráficos regulares (ciclos ímpares em particular) - conexões com a teoria espectral

10

A publicação está relacionada a: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

A que distância o Lovasz está vinculado à capacidade de erro zero dos gráficos regulares? Existem exemplos em que se sabe que o limite de Lovasz não é igual à capacidade de erro zero de um gráfico regular? (Isso foi respondido abaixo por Oleksandr Bondarenko.)

Em particular, existe alguma desigualdade estrita conhecida por ciclos ímpares de lados maiores ou iguais a 7 ?

Atualização Que melhoria é necessária na teoria espectral para melhorar a função teta de Lovasz, de modo que a lacuna entre a capacidade de Shannon e a Lovasz Theta para os casos em que existe uma lacuna possa ser reduzida? (Note que estou preocupado apenas da perspectiva espectral)

T ....
fonte
Eu apaguei minha resposta errada. Obrigado pela correção!
Hsien-Chih Chang
ϑ
δ=ϑΘϑΘϑδ>0

Respostas:

13

GΘ(G)a´ϑ(G)[1]a¨ GΘ(G)7<ϑ(G)=9

Em , note-se que "Os limites superiores mais conhecidos em e para ímpar e maior que são dados pela função teta de Lovasz ...". A partir disso, concluo que a resposta para sua última pergunta é não (desde então não conheço nenhum resultado melhorando isso).[2]Θ(Cm)Θ(C¯m)m5

Encontrar a capacidade de Shannon mesmo para seria um grande avanço para esse problema difícil. Além disso, pode-se notar queC7

"não se sabe se o problema de decidir se a capacidade de Shannon de um dado gráfico de entrada excede um determinado valor é decidível".

  1. W. Haemers, “ Em alguns problemas de Lov sz com relação à capacidade de Shannon de um gráficoa´ ”, IEEE Trans. em Teoria da Informação, vol. 25, n. 2, pp. 231-232, março de 1979.
  2. T. Bohman, " Um teorema do limite para as capacidades de Shannon de ciclos ímpares. II ," Proceedings of American Mathematical Society, 2005.
  3. N. Alon, " Raciocínio Combinatório na Teoria da Informação ".
Oleksandr Bondarenko
fonte
Muito obrigado. O mesmo é conhecido para ciclos ímpares simples? Por exemplo polígono de lados? 7
T ....
11
Então, não se sabe. Isto é muito interessante.
T ....