О пределе, связанном с преобразованием хроматического многочлена

Question

Я играл с хроматическим многочленом (здесь обозначен $\chi_G(x)$), и я сделал следующее предположение.

Позволять $(G_n)_{n \ge 1}$ последовательность графов с $v(G_n) \to \infty$ ($v(G_n)$ обозначает количество вершин $G_n$) а также $e(G_n) \to \infty$ ($e(G_n)$ обозначает количество ребер $G_n$).

Для каждого $x \neq 0$, определим следующее преобразование хроматического полинома $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). $$

Гипотеза состоит в том, что для каждого фиксированного действительного числа $x \neq 0$, у нас есть $\psi_{G_n}(x) \to \exp(-x)$ в виде $n$ уходит в бесконечность.

Я проверил гипотезу для нескольких последовательностей графиков: например, $G_n$ являясь полным графом $K_n$, для $G_n$ быть деревом на $n$ вершины и для $G_n$ будучи собранием $n$ независимые края (совпадение по $2n$ вершины).

Кто-нибудь знает, хорошо ли это известно?

PS: Я не уверен, что условия на $v(G_n)$ а также $e(G_n)$правильный. Также приветствуются любые комментарии по этому поводу.

Answer 1

Вот эвристический аргумент, который, возможно, кому-то удастся привести строгое. я пишу$v_n=v(G_n)$ а также $e_n=e(G_n)$. Позволять$$ \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. $$ Я утверждаю, что для фиксированного $k\geq 0$, $$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$ Можно доказать это, заметив, что (например, по теореме о неисправности цепи, которая показывает, что $c_{n,v_n-k}$ увеличивается по мере добавления ребер к $G_n$) $c_{n,v_n-k}$ ограничено снизу своим значением, когда $G_n$ является деревом и ограничено сверху своим значением, когда $G_n$является полным графом. Заявленный результат легко проверяется для деревьев и полных графов (в последнем случае с использованием известной асимптотики для чисел Стирлинга первого рода). Возможно, есть более прямое доказательство, но в любом случае, если мы не будем беспокоиться об обосновании взаимозаменяемости лимитов и сумм, мы получим$$ \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). $$