Em um limite envolvendo uma transformada do polinômio cromático
Eu estava brincando com o polinômio cromático (denotado aqui por$\chi_G(x)$) e fiz a seguinte conjectura.
Deixar$(G_n)_{n \ge 1}$ser uma sequência de gráficos com$v(G_n) \to \infty$($v(G_n)$denota o número de vértices de$G_n$) e$e(G_n) \to \infty$($e(G_n)$denota o número de arestas de$G_n$).
Para cada$x \neq 0$, vamos definir a seguinte transformada do polinômio 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). $$
A conjectura é que para cada número real fixo$x \neq 0$, temos$\psi_{G_n}(x) \to \exp(-x)$Como$n$vai ao infinito.
Eu verifiquei a conjectura para algumas sequências de gráficos: por exemplo,$G_n$sendo o gráfico completo$K_n$, por$G_n$sendo uma árvore em$n$vértices e para$G_n$sendo uma coleção de$n$arestas independentes (uma correspondência em$2n$vértices).
Alguém sabe se isso é conhecido?
PS: Não tenho certeza se as condições em$v(G_n)$e$e(G_n)$são os certos. Qualquer comentário sobre isso também é bem-vindo.
Respostas
Aqui está um argumento heurístico que talvez alguém possa tornar rigoroso. escrevo$v_n=v(G_n)$e$e_n=e(G_n)$. Deixar$$ \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. $$Eu afirmo que para fixo$k\geq 0$,$$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$Pode-se provar isso observando que (pelo Teorema do Circuito Quebrado, por exemplo, que mostra que$c_{n,v_n-k}$aumenta à medida que adicionamos mais arestas a$G_n$)$c_{n,v_n-k}$é limitada abaixo pelo seu valor quando$G_n$é uma árvore e é limitada superiormente por seu valor quando$G_n$é um gráfico completo. O resultado reivindicado é facilmente verificado para árvores e grafos completos (no último caso, usando assintóticas conhecidas para os números de Stirling do primeiro tipo). Talvez haja uma prova mais direta, mas de qualquer forma, se não nos preocuparmos em justificar a troca de limites e somas, obtemos$$ \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). $$