ขีด จำกัด ที่เกี่ยวข้องกับการแปลงของพหุนามสี
ฉันกำลังเล่นกับพหุนามสี (แสดงที่นี่โดย $\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)$เป็นคนที่ใช่ ความคิดเห็นใด ๆ เกี่ยวกับเรื่องนี้ยินดีต้อนรับเช่นกัน
คำตอบ
นี่คือการโต้เถียงแบบฮิวริสติกซึ่งอาจมีคนพูดอย่างเข้มงวดได้ ฉันเขียน$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!}. $$ เราสามารถพิสูจน์สิ่งนี้ได้โดยสังเกตว่า (โดย Broken Circuit Theorem เป็นต้นซึ่งแสดงให้เห็นว่า $c_{n,v_n-k}$ เพิ่มขึ้นเมื่อเราเพิ่มขอบมากขึ้น $G_n$) $c_{n,v_n-k}$ ถูกล้อมรอบด้านล่างด้วยค่าเมื่อ $G_n$ เป็นต้นไม้และถูกล้อมรอบด้วยมูลค่าของมันเมื่อ $G_n$เป็นกราฟที่สมบูรณ์ ผลลัพธ์ที่อ้างสิทธิ์นั้นสามารถตรวจสอบได้อย่างง่ายดายสำหรับต้นไม้และกราฟที่สมบูรณ์ (ในกรณีหลังนี้ใช้ asymptotics ที่รู้จักกันสำหรับหมายเลข Stirling ประเภทแรก) บางทีอาจมีข้อพิสูจน์ที่ตรงกว่า แต่ในกรณีใด ๆ หากเราไม่กังวลเกี่ยวกับการกำหนดข้อ จำกัด และผลรวมการแลกเปลี่ยน$$ \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). $$