En un límite que involucra una transformada del polinomio cromático

Question

Estaba jugando con el polinomio cromático (indicado aquí por$\chi_G(x)$) y he hecho la siguiente conjetura.

Dejar$(G_n)_{n \ge 1}$sea ​​una sucesión de gráficas con$v(G_n) \to \infty$($v(G_n)$denota el número de vértices de$G_n$) y$e(G_n) \to \infty$($e(G_n)$denota el número de aristas de$G_n$).

Para cada$x \neq 0$, definamos la siguiente transformada del polinomio cromático de$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). $$

La conjetura es que para cada número real fijo$x \neq 0$, tenemos$\psi_{G_n}(x) \to \exp(-x)$como$n$va al infinito.

He comprobado la conjetura de algunas secuencias de gráficos: por ejemplo,$G_n$siendo el grafo completo$K_n$, por$G_n$ser un árbol en$n$vértices y para$G_n$siendo una colección de$n$aristas independientes (un emparejamiento en$2n$vértices).

¿Alguien sabe si esto es conocido?

PD: No estoy seguro si las condiciones en$v(G_n)$y$e(G_n)$son los correctos. Cualquier comentario sobre esto es bienvenido también.

Answer 1

Aquí hay un argumento heurístico que quizás alguien pueda hacer riguroso. yo escribo$v_n=v(G_n)$y$e_n=e(G_n)$. Dejar$$ \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. $$Yo afirmo que por fijo$k\geq 0$,$$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$Uno puede probar esto observando que (por el Teorema del Circuito Roto, por ejemplo, que muestra que$c_{n,v_n-k}$aumenta a medida que agregamos más bordes a$G_n$)$c_{n,v_n-k}$está acotado por debajo por su valor cuando$G_n$es un árbol, y está acotado arriba por su valor cuando$G_n$es un grafo completo. El resultado reclamado se verifica fácilmente para árboles y gráficos completos (en el último caso, utilizando asintóticas conocidas para los números de Stirling del primer tipo). Quizá haya una demostración más directa, pero en cualquier caso, si no nos preocupamos de justificar el intercambio de límites y sumas, obtenemos$$ \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). $$