Su un limite che comporta una trasformata del polinomio cromatico

Aug 16 2020

Stavo giocando con il polinomio cromatico (indicato qui con$\chi_G(x)$) e ho fatto la seguente congettura.

Permettere$(G_n)_{n \ge 1}$essere una sequenza di grafici con$v(G_n) \to \infty$($v(G_n)$denota il numero di vertici di$G_n$) e$e(G_n) \to \infty$($e(G_n)$denota il numero di spigoli di$G_n$).

Per ciascuno$x \neq 0$, definiamo la seguente trasformata del polinomio cromatico di$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 congettura è che per ogni numero reale fisso$x \neq 0$, noi abbiamo$\psi_{G_n}(x) \to \exp(-x)$come$n$va all'infinito.

Ho verificato la congettura per alcune sequenze di grafici: ad esempio,$G_n$essendo il grafico completo$K_n$, per$G_n$essere un albero su$n$vertici e per$G_n$essere una raccolta di$n$spigoli indipendenti (una corrispondenza su$2n$vertici).

Qualcuno sa se è noto?

PS: non sono sicuro se le condizioni su$v(G_n)$e$e(G_n)$sono quelli giusti. Sono graditi anche eventuali commenti in merito.

Risposte

6 RichardStanley Aug 17 2020 at 01:22

Ecco un argomento euristico che forse qualcuno può rendere rigoroso. Scrivo io$v_n=v(G_n)$e$e_n=e(G_n)$. Permettere$$ \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. $$Lo rivendico per fisso$k\geq 0$,$$ \lim_{n\to\infty} \frac{c_{n,v_n-k}}{e_n^k} = \frac{1}{k!}. $$Si può dimostrare ciò osservando che (dal Teorema del Circuito Interrotto, per esempio, che lo dimostra$c_{n,v_n-k}$aumenta man mano che aggiungiamo più spigoli a$G_n$)$c_{n,v_n-k}$è delimitato sotto dal suo valore quando$G_n$è un albero ed è delimitato in alto dal suo valore quando$G_n$è un grafico completo. Il risultato dichiarato è facilmente verificabile per alberi e grafi completi (in quest'ultimo caso, utilizzando asintotici noti per i numeri di Stirling del primo tipo). Forse c'è una prova più diretta, ma in ogni caso, se non ci preoccupiamo di giustificare lo scambio di limiti e somme, otteniamo$$ \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). $$