Über eine Grenze, die eine Transformation des chromatischen Polynoms beinhaltet
Ich habe mit dem chromatischen Polynom herumgespielt (hier bezeichnet mit$\chi_G(x)$) und ich habe folgende Vermutung aufgestellt.
Lassen$(G_n)_{n \ge 1}$sei eine Folge von Graphen mit$v(G_n) \to \infty$($v(G_n)$bezeichnet die Anzahl der Ecken von$G_n$) und$e(G_n) \to \infty$($e(G_n)$bezeichnet die Anzahl der Kanten von$G_n$).
Für jeden$x \neq 0$, lassen Sie uns die folgende Transformation des chromatischen Polynoms von definieren$G_n$ $$ \psi_{G_n}(x) = \frac{x^{v(G_n)}}{e(G_n)^{v(G_n)}} \chi_{G_n}\left( \frac{e(G_n)}{x} \right). $$
Die Vermutung ist die für jede feste reelle Zahl$x \neq 0$, wir haben$\psi_{G_n}(x) \to \exp(-x)$wie$n$geht ins Unendliche.
Ich habe die Vermutung für einige Folgen von Graphen überprüft: zum Beispiel$G_n$ist der vollständige Graph$K_n$, zum$G_n$ein Baum zu sein$n$Ecken und für$G_n$eine Sammlung von sein$n$unabhängige Kanten (ein Matching on$2n$Eckpunkte).
Weiß jemand ob das bekannt ist?
PS: Ich bin mir nicht sicher, ob die Bedingungen auf$v(G_n)$und$e(G_n)$sind die Richtigen. Kommentare hierzu sind ebenfalls willkommen.
Antworten
Hier ist ein heuristisches Argument, das vielleicht jemand rigoros machen kann. Ich schreibe$v_n=v(G_n)$und$e_n=e(G_n)$. Lassen$$ \chi_{G_n}(x) = x^{v_n}-c_{n,v_n-1} x^{v_n-1}+c_{n,v_n-2}x^{v_n-2}-\cdots. $$Ich behaupte das für fest$k\geq 0$,$$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$Man kann dies beweisen, indem man das feststellt (zum Beispiel durch das Broken-Circuit-Theorem, das das zeigt$c_{n,v_n-k}$nimmt zu, wenn wir weitere Kanten hinzufügen$G_n$)$c_{n,v_n-k}$wird nach unten durch seinen Wert wenn begrenzt$G_n$ein Baum ist und nach oben durch seinen Wert begrenzt wird$G_n$ist ein vollständiger Graph. Das behauptete Ergebnis lässt sich leicht für Bäume und vollständige Graphen verifizieren (im letzteren Fall unter Verwendung bekannter Asymptotik für die Stirling-Zahlen der ersten Art). Vielleicht gibt es einen direkteren Beweis, aber auf jeden Fall, wenn wir uns keine Gedanken darüber machen, das Vertauschen von Grenzen und Summen zu rechtfertigen, bekommen wir es$$ \lim_{n\to\infty} \frac{x^{v_n}}{e_n^{v_n}}\chi_{G_n}\left( \frac{e_n}{x}\right) = \sum_{k\geq 0} \lim_{n\to\infty} \frac{(-1)^k c_{n,v_n-k}x^k}{e_n^k} $$ $$ \qquad = \sum_{k\geq 0} \frac{(-1)^k x^k}{k!} = \exp(-x). $$