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

10

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)

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"? ϑ
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. δ=ϑΘΘ ϑ δ > 0ϑΘϑδ>0
T ....

Antworten:

13

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Θ(G)a´ϑ(G)[1]a¨ GΘ(G)7<ϑ(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]Θ(Cm)Θ(C¯m)m5

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

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

  1. W. Haemers, " Zu einigen Problemen von Lov sz bezüglich der Shannon-Kapazität eines Graphena´ ", IEEE Trans. on Information Theory, vol. 25, nein. 2, S. 231–232, März 1979.
  2. T. Bohman, " Ein Grenzwertsatz für die Shannon-Kapazitäten ungerader Zyklen. II ", Proceedings of the American Mathematical Society, 2005.
  3. 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
T ....
1
SO ist es nicht bekannt. Das ist sehr interessant.
T ....