Lovasz-Theta-Funktion und reguläre Graphen (insbesondere ungerade Zyklen)

Lovasz-Theta-Funktion und reguläre Graphen (insbesondere ungerade Zyklen) - Verbindungen zur Spektraltheorie

Der Beitrag bezieht sich auf: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

Wie weit ist der Lovasz von der Null-Fehler-Kapazität regulärer Graphen entfernt? Gibt es Beispiele, bei denen bekannt ist, dass die Lovasz-Grenze nicht der Null-Fehler-Kapazität eines regulären Graphen entspricht? (Dies wurde unten von Oleksandr Bondarenko beantwortet.)

Ist insbesondere eine strikte Ungleichung für ungerade Zyklen von Seiten größer oder gleich ? $7$

Update Welche Verbesserung ist in der Spektraltheorie erforderlich, um die Lovasz-Theta-Funktion zu verbessern, damit die Lücke zwischen Shannon-Kapazität und Lovasz-Theta für die Fälle, für die eine Lücke besteht, verringert werden kann? (Hinweis Ich bin nur aus spektraler Sicht besorgt)

graph-theory it.information-theory T ....
quelle

Ich habe meine falsche Antwort gelöscht. Danke für die Korrektur!

Hsien-Chih Chang 28 之

Ich verstehe das Update nicht. Wenn es eine Lücke zwischen der Null-Fehler-Kapazität und , wie können Sie es "senken"?

ϑ

$\vartheta$

Sasho Nikolov

Ich denke, die Formulierung ist schlecht. Angenommen, ist die Kapazitätslücke zwischen und . Wenn die spektraltheoretische Technologie etwas verbessert werden könnte, so dass die neue Technik eine schärfere Obergrenze im Vergleich zu ergibt, wenn , was könnte diese mögliche Verbesserung in der spektraltheoretischen Technologie sein? Grundsätzlich fragt das Update, ob die Spektraltheorie ab heute solchen Verbesserungsblockaden gegenübersteht.

δ = ϑ - Θ

$\delta=\vartheta-\Theta$

ϑ

$\vartheta$

Θ

$\Theta$

ϑ

$\vartheta$

δ > 0

$\delta>0$

T ....

Antworten:

Tatsächlich ist ein regulärer Graph für den die Null-Fehler-Kapazität kleiner ist als die Lov sz-gebundene . W. Haemers in hat bewiesen, dass für das Komplement von Schl fli graph Folgendes gilt: . $G$ $\Theta(G)$ $\acute{a}$ $\vartheta(G)$ $[1]$ $\ddot{a}$ $G$ $\Theta(G)\leqslant7<\vartheta(G)=9$

In wird angemerkt, dass "die bekanntesten Obergrenzen für und für ungerade und größer als durch die Lovasz-Theta-Funktion gegeben sind ...". Daraus schließe ich, dass die Antwort auf Ihre letzte Frage Nein lautet (seitdem kenne ich keine Ergebnisse, die dies verbessern). $[2]$ $\Theta(C_m)$ $\Theta(\overline{C}_m)$ $m$ $5$

Die Shannon-Kapazität selbst für wäre ein großer Durchbruch für dieses schwierige Problem. Zusätzlich kann das bemerkt werden $C_7$

"Es ist nicht bekannt, ob das Problem der Entscheidung, ob die Shannon-Kapazität eines bestimmten Eingabegraphen einen bestimmten Wert überschreitet, entscheidbar ist."

W. Haemers, " Zu einigen Problemen von Lov sz bezüglich der Shannon-Kapazität eines Graphen $\acute{a}$ ", IEEE Trans. on Information Theory, vol. 25, nein. 2, S. 231–232, März 1979.
T. Bohman, " Ein Grenzwertsatz für die Shannon-Kapazitäten ungerader Zyklen. II ", Proceedings of the American Mathematical Society, 2005.
N. Alon, " Kombinatorisches Denken in der Informationstheorie ".

Oleksandr Bondarenko
quelle

Vielen Dank. Ist das gleiche für einfache ungerade Zyklen bekannt? Zum Beispiel seitiges Polygon?

7

$7$

T ....

SO ist es nicht bekannt. Das ist sehr interessant.

T ....