Na granicy obejmującej transformację wielomianu chromatycznego

Question

Bawiłem się wielomianem chromatycznym (oznaczonym tutaj przez $\chi_G(x)$) i poczyniłem następującą hipotezę.

Pozwolić $(G_n)_{n \ge 1}$ być sekwencją wykresów z $v(G_n) \to \infty$ ($v(G_n)$ oznacza liczbę wierzchołków $G_n$) i $e(G_n) \to \infty$ ($e(G_n)$ oznacza liczbę krawędzi $G_n$).

Dla każdego $x \neq 0$zdefiniujmy następującą transformację wielomianu chromatycznego $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). $$

Przypuszcza się, że dla każdej ustalonej liczby rzeczywistej $x \neq 0$, mamy $\psi_{G_n}(x) \to \exp(-x)$ tak jak $n$ idzie w nieskończoność.

Sprawdziłem przypuszczenie dla kilku sekwencji wykresów: na przykład $G_n$ będący pełnym wykresem $K_n$, dla $G_n$ bycie drzewem $n$ wierzchołki i dla $G_n$ będąc zbiorem $n$ niezależne krawędzie (dopasowanie na $2n$ wierzchołki).

Czy ktoś wie, czy to jest dobrze znane?

PS: Nie jestem pewien, czy warunki są włączone $v(G_n)$ i $e(G_n)$są właściwe. Wszelkie komentarze na ten temat również są mile widziane.

Answer 1

Oto heurystyczny argument, który być może ktoś może zaostrzyć. piszę$v_n=v(G_n)$ i $e_n=e(G_n)$. Pozwolić$$ \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. $$ Twierdzę, że to ustalone $k\geq 0$, $$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$ Można to udowodnić, zauważając to (na przykład twierdzenie o zerwanym obwodzie, które to pokazuje $c_{n,v_n-k}$ rośnie, gdy dodajemy więcej krawędzi $G_n$) $c_{n,v_n-k}$ jest ograniczona poniżej wartością when $G_n$ jest drzewem i jest ograniczone powyżej jego wartością kiedy $G_n$jest pełnym wykresem. Twierdzony wynik można łatwo zweryfikować dla drzew i pełnych wykresów (w tym drugim przypadku przy użyciu znanych asymptotyków dla liczb Stirlinga pierwszego rodzaju). Być może istnieje bardziej bezpośredni dowód, ale w każdym razie, jeśli nie martwimy się o uzasadnienie zamiany limitów i kwot, otrzymujemy$$ \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). $$