Fonction thêta de Lovasz et graphes réguliers (cycles impairs en particulier)

Fonction thêta de Lovasz et graphes réguliers (cycles impairs en particulier) - connexions à la théorie spectrale

Le message est lié à: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

À quelle distance le Lovasz est-il lié à la capacité sans erreur des graphiques réguliers? Existe-t-il des exemples où la limite de Lovasz est connue pour ne pas être égale à la capacité d'erreur zéro d'un graphique régulier? (Cela a été répondu ci-dessous par Oleksandr Bondarenko.)

En particulier, existe-t-il une inégalité stricte connue pour les cycles impairs de côtés supérieurs ou égaux à ? $7$

Mise à jour Quelle amélioration est nécessaire dans la théorie spectrale pour améliorer la fonction thêta de Lovasz afin que l'écart entre la capacité de Shannon et Lovasz Theta pour les cas pour lesquels un écart existe puisse être réduit? (Notez que je ne suis concerné que du point de vue spectral)

graph-theory it.information-theory T ....
la source

J'ai supprimé ma mauvaise réponse. Merci pour la correction!

Hsien-Chih Chang 張顯之

Je ne comprends pas la mise à jour, s'il y a un écart entre la capacité sans erreur et , comment pouvez-vous la "baisser"?

ϑ

$\vartheta$

Sasho Nikolov

Je pense que la formulation est mauvaise. Disons que est l'écart de capacité entre et . Si une certaine amélioration pouvait être apportée à la technologie de la théorie spectrale de sorte que la nouvelle technique donne une limite supérieure plus nette par rapport à lorsque , quelle pourrait être cette amélioration possible dans la technologie de la théorie spectrale? Fondamentalement, la mise à jour demande si la théorie spectrale est confrontée à de tels obstacles à l'amélioration.

δ = ϑ - Θ

$\delta=\vartheta-\Theta$

ϑ

$\vartheta$

Θ

$\Theta$

ϑ

$\vartheta$

δ > 0

$\delta>0$

T ....

Réponses:

En fait, il est connu un graphe régulier pour lequel la capacité d'erreur nulle est inférieure à la Lov sz liée . W. Haemers dans a prouvé que pour le complément de Schl fli graph ce qui suit vaut: . $G$ $\Theta(G)$ $\acute{a}$ $\vartheta(G)$ $[1]$ $\ddot{a}$ $G$ $\Theta(G)\leqslant7<\vartheta(G)=9$

Dans il est noté que "Les limites supérieures les plus connues sur et pour impair et supérieur à sont données par la fonction thêta de Lovasz ...". J'en conclus que la réponse à votre dernière question est non (depuis lors, je ne connais aucun résultat améliorant cela.). $[2]$ $\Theta(C_m)$ $\Theta(\overline{C}_m)$ $m$ $5$

Trouver la capacité de Shannon même pour serait une percée majeure pour ce problème difficile. De plus, on peut remarquer que $C_7$

"on ne sait pas si le problème de décider si la capacité de Shannon d'un graphique d'entrée donné dépasse une valeur donnée est décidable".

W. Haemers, « Sur certains problèmes de Lov sz concernant la capacité de Shannon d'un graphe $\acute{a}$ », IEEE Trans. sur la théorie de l'information, vol. 25, non. 2, p. 231-232, mars 1979.
T. Bohman, « Un théorème limite pour les capacités de Shannon des cycles impairs. II », Actes de l'American Mathematical Society, 2005.
N. Alon, " Raisonnement combinatoire en théorie de l'information ".

Oleksandr Bondarenko
la source

Merci beaucoup. Est-ce la même chose pour les cycles impairs simples? Par exemple, un polygone à côtés?

7

$7$

T ....

Donc ce n'est pas connu. C'est très intéressant.

T ....