Sur une limite impliquant une transformée du polynôme chromatique

Question

Je jouais avec le polynôme chromatique (noté ici par$\chi_G(x)$) et j'ai fait la conjecture suivante.

Laisser$(G_n)_{n \ge 1}$être une suite de graphes avec$v(G_n) \to \infty$($v(G_n)$désigne le nombre de sommets de$G_n$) et$e(G_n) \to \infty$($e(G_n)$désigne le nombre d'arêtes de$G_n$).

Pour chaque$x \neq 0$, définissons la transformée suivante du polynôme chromatique 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 conjecture est que pour chaque nombre réel fixe$x \neq 0$, Nous avons$\psi_{G_n}(x) \to \exp(-x)$comme$n$va à l'infini.

J'ai vérifié la conjecture pour quelques séquences de graphes : par exemple,$G_n$étant le graphe complet$K_n$, pour$G_n$être un arbre sur$n$sommets et pour$G_n$étant une collection de$n$arêtes indépendantes (un appariement sur$2n$sommets).

Est-ce que quelqu'un sait si c'est bien connu ?

PS : je ne sais pas si les conditions sur$v(G_n)$et$e(G_n)$sont la bonne. Tout commentaire à ce sujet est également le bienvenu.

Answer 1

Voilà un argument heuristique que quelqu'un peut peut-être rendre rigoureux. j'écris$v_n=v(G_n)$et$e_n=e(G_n)$. Laisser$$ \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. $$Je prétends que pour fixe$k\geq 0$,$$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$On peut le prouver en notant que (par le théorème du circuit brisé, par exemple, qui montre que$c_{n,v_n-k}$augmente à mesure que nous ajoutons plus d'arêtes à$G_n$)$c_{n,v_n-k}$est délimité en dessous par sa valeur lorsque$G_n$est un arbre, et est borné au-dessus par sa valeur quand$G_n$est un graphique complet. Le résultat revendiqué est facilement vérifié pour les arbres et les graphes complets (dans ce dernier cas, en utilisant des asymptotiques connues pour les nombres de Stirling du premier type). Il y a peut-être une preuve plus directe, mais en tout cas, si on ne se soucie pas de justifier l'interchangeabilité des limites et des sommes, on obtient$$ \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). $$