Artikel

5.3: Deletion-Contraction und das Chromatische Polynom


Übung 243.

In Kapitel 2 haben wir die Deletion-Contraction-Recurrence zum Zählen aufspannender Bäume eines Graphen eingeführt. Finden Sie heraus, wie das chromatische Polynom eines Graphen mit denen zusammenhängt, die sich aus dem Löschen einer Kante e und der Kontraktion derselben Kante e ergeben. Versuchen Sie eine Rekursion zu finden, wie sie beim Zählen aufspannender Bäume das chromatische Polynom eines Graphen durch die chromatischen Polynome von (G − e) und (G/e) für eine beliebige Kante e ausdrückt. Verwenden Sie diese Rekursion, um einen weiteren Beweis dafür zu liefern, dass die Anzahl der Möglichkeiten, einen Graphen mit x Farben einzufärben, eine Polynomfunktion von (x) ist. Online-Hinweis.

Übung 244

Verwenden Sie die Deletion-Contraction-Recurrence, um die Berechnung des chromatischen Polynoms des Graphen in Abbildung 5.1 auf die Berechnung chromatischer Polynome zu reduzieren, die Sie leicht berechnen können. (Sie können Ihre Berechnungen vereinfachen, indem Sie sich die Auswirkungen des Löschens einer Kante, die eine Schleife ist, oder einer von mehreren Kanten zwischen denselben beiden Scheitelpunkten auf das chromatische Polynom auswirken.)

Abbildung 5.1: Ein Diagramm.

Ausübung

  1. Auf wie viele Arten können Sie die Scheitelpunkte eines Pfads auf n Scheitelpunkten mit x Farben richtig einfärben? Beschreiben Sie die Abhängigkeit des chromatischen Polynoms eines Pfades von der Anzahl der Knoten.
  2. ∗(Nicht sehr schwer.) Auf wie viele Arten können Sie die Ecken eines Kreises auf n Ecken mit (x) Farben richtig einfärben? Beschreiben Sie die Abhängigkeit des chromatischen Polynoms eines Kreises von der Anzahl der Ecken. Online-Hinweis.

Übung 246

Auf wie viele Arten können Sie die Scheitelpunkte eines Baums auf n Scheitelpunkten mit (x)-Farben richtig einfärben?

Übung 247

Was beobachten Sie an den Vorzeichen der Koeffizienten des chromatischen Polynoms des Graphen in Abbildung 5.1? Wie sieht es mit den Vorzeichen der Koeffizienten des chromatischen Polynoms eines Weges aus? Von einem Zyklus? Von einem Baum? Machen Sie eine Vermutung über die Vorzeichen der Koeffizienten eines chromatischen Polynoms und beweisen Sie diese.


Wie erhalte ich das chromatische Polynom von $C_5$?

Ich habe einige Bücher über chromatische Polynome gelesen, ich bin ein wenig verwirrt über das Verfahren, das erforderlich ist, um sie zu erhalten. Ich habe in einem Buch gelesen, dass das chromatische Polynom durch Partitionieren von $V$ in unabhängige Mengen erhalten wird. Wenn wir $f(r)$ Möglichkeiten haben, diese Partition zu machen, dann haben wir im Allgemeinen:

denn wenn wir jede Unabhängigkeit in einem einzigartigen Knoten zusammenziehen, erhalten wir eine Clique $K_r$.

Es ist nicht ganz klar, was ich tun soll. Im Fall von $C_5$ sollte ich es wohl auf alle möglichen unabhängigen Mengen aufteilen, aber es ist nicht wirklich klar, wie ich $f(r)$ erhalten soll.


Chromatische symmetrische Funktion von Graphen aus Borcherds Algebren

Die Weyl-Nenneridentität hat interessante kombinatorische Eigenschaften für mehrere Klassen von Lie-Algebren. Damit beweisen wir, dass für einen endlichen Graphen g, kann die chromatisch-symmetrische Funktion X G aus der Weyl-Nenneridentität einer Borcherds-Kac-Moody-Lie-Algebra g gewonnen werden, deren zugehöriger Graph ist g. Dies ergibt eine Verbindung zwischen (a) den Koeffizienten, die auftreten, wenn die chromatische symmetrische Funktion X G durch die symmetrischen Potenzsummenfunktionen ausgedrückt wird, und (b) den Wurzelmultiplizitäten der Borcherds-Algebra g . Aus diesem Ergebnis leiten wir einen Lie-theoretischen Beweis verschiedener alternativer Ausdrücke der von Stanley erhaltenen chromatischen symmetrischen Funktion ab. Beispiele, die Lie-Algebren mit kleinem Rang verwenden, werden bereitgestellt, um unsere Ergebnisse zu veranschaulichen.

Der Absolutwert des linearen Koeffizienten des chromatischen Polynoms von g ist als chromatische Diskriminante von bekannt g. Als Anwendung unseres Hauptsatzes identifizieren wir einen in X G auftretenden Koeffizienten, der der chromatischen Diskriminante entspricht. Wir finden auch einen Zusammenhang zwischen dem Weyl-Nenner und dem g-elementare symmetrische Funktionen. Mit diesem Zusammenhang führen wir einen Lie-theoretischen Beweis der Nicht-Negativität von Koeffizienten von g-Symmetrische Funktionen der Potenzsumme.